Apparently, this is only a problem when executed by "root" and not by a non-priviliged user.
The following patch instructs zip to not follow the symlinks, but to just store them as-is:
diff --git a/tools/releasetools/non_ab_ota.py b/tools/releasetools/non_ab_ota.py
index 6cd01e401a..bbc5000f10 100644
--- a/tools/releasetools/non_ab_ota.py
+++ b/tools/releasetools/non_ab_ota.py
@@ -605,7 +605,7 @@ def GenerateNonAbOtaPackage(target_file, output_file, source_file=None):
tmpfile = common.MakeTempFile(suffix=".zip")
os.unlink(tmpfile)
common.RunAndCheckOutput(
- ["zip", tmpfile, "-r", ".", "-0"], cwd=target_file)
+ ["zip", tmpfile, "-y", "-r", ".", "-0"], cwd=target_file)
assert zipfile.is_zipfile(tmpfile)
target_file = tmpfile