[Android Software/Hacking General [Developers Only]] osm0sis:
I think I found a solution that preserves app data, forces things to optimize, then manually cleans up on AOSP-based ROMs, all while leaving packages.xml in working order! :D :cowboy:

/system/etc/init.d/000gappsintegrator:

#!/system/bin/sh
# chmod -R 755 /system/etc/init.d
#
# ROM GApps Auto-Integration
# osm0sis @ xda-developers

gtmp=/data/local/tmp/gapp;
log=/sdcard/gapps-integrator.log;

test ! -f $log && echo -e "## GApps Auto-Integration Script Log\n" > $log;
echo -n `date` >> $log;

# get SDK version to perform different actions due to /data/app layout changes
sdkver=`getprop ro.build.version.sdk`;

# find new unintegrated Google Apps APKs in /data
for i in $(ls /data/app/ | grep -E 'com.android|com.google.android'); do

# find equivalent /system APK name and only process if it exists
xml=/data/system/packages.xml;
package=`echo $i | cut -d- -f1`;
sysapk=`grep "updated-package name=\"$package" $xml | grep -o 'codePath=.*$' | cut -d\" -f2`;

echo -ne "\n/data/app/$i $sysapk" >> $log;

if [ "$sysapk" ]; then

# compare /data and /system APK versions and only integrate if /data is newer (necessary on Lollipop and above)
datver=$(grep "codePath=\"/data/app/$i" $xml | grep -o 'version=.*$' | cut -d\" -f2);
sysver=$(grep "codePath=\"$sysapk" $xml | grep -o 'version=.*$' | cut -d\" -f2);

if [ "$datver" -gt "$sysver" ]; then

echo -n " ($datver > $sysver)" >> $log;

# KitKat (and below) support
if [ "$sdkver" -le 20 ]; then

# extract and force copy libraries to /system
mkdir -p $gtmp;
unzip /data/app/$i -d $gtmp;
chmod 644 $gtmp/lib/arm*/*;
mount -o remount,rw /system;
cp -fp $gtmp/lib/arm*/* /system/lib/;
rm -rf $gtmp;

# overwrite /system APK with new /data APK then fix permissions
cp -f /data/app/$i $sysapk;
chown root.root $sysapk;
chmod 644 $sysapk;

# Lollipop support
elif [ "$sdkver" -le 22 ]; then

# force copy libraries to /system respecting symlinks then clean up empty files
mount -o remount,rw /system;
cp -RLf /data/app/$i/lib $sysapk;
for j in `ls $sysapk/lib/arm*/*`; do
test ! -s $j && rm -f $j;
done;

# overwrite /system APK with new /data APK then fix permissions
cp -fp /data/app/$i/base.apk $sysapk/`basename $sysapk`.apk;
chown -R root.root $sysapk;
chmod 644 $sysapk/lib/arm*/*;

# update packages.xml entry for the /system APK and remove entry for /data APK
sed -i "s#<package name=\"${package}\" codePath=\"/data/app/${i}\" nativeLibraryPath=\"/data/app/${i}/lib\" \(.*\) installer=\"com.android.vending\">#<package name=\"${package}\" codePath=\"${sysapk}\" nativeLibraryPath=\"${sysapk}/lib\" \1>#";
sed -i -e "/<updated-package name=\"${package}/,/<\/updated-package>/d" $xml;

# flag for cleanup on reboot following optimization
touch /data/app/$i/integrated;

# Marshmallow (and above) support
elif [ "$sdkver" -ge 23 ]; then

# if necessary force copy libraries to /system respecting symlinks then clean up empty files
mount -o remount,rw /system;
if [ -d $sysapk/lib ]; then
cp -RLf /data/app/$i/lib $sysapk;
for j in `ls $sysapk/lib/arm*/*`; do
test ! -s $j && rm -f $j;
done;
fi;

# if necessary force copy APK odex file to /system
if [ -d $sysapk/oat ]; then
cp -fp /data/app/$i/oat/arm*/base.odex $sysapk/oat/arm*/`basename $sysapk`.odex;
fi;

# overwrite /system APK with new /data APK then fix permissions
cp -fp /data/app/$i/base.apk $sysapk/`basename $sysapk`.apk;
chown -R root.root $sysapk;
chmod 644 $sysapk/lib/arm*/* $sysapk/oat/arm*/*;

# update packages.xml entry for the /system APK
sed -i "s#<package name=\"${package}\" codePath=\"/data/app/${i}\" nativeLibraryPath=\"/data/app/${i}/lib\" \(.*\) installer=\"com.android.vending\">#<package name=\"${package}\" codePath=\"${sysapk}\" nativeLibraryPath=\"${sysapk}/lib\" \1>#";
sed -i -e "/<updated-package name=\"${package}/,/<\/updated-package>/d" $xml;

# flag for cleanup on reboot following optimization
touch /data/app/$i/integrated;

fi;
mount -o remount,ro /system;

fi;
elif [ -f /data/app/$i/integrated ]; then

# clean up to mimic pre-Lollipop (AOSP) behavior
rm -rf /data/app/$i;

fi;
done;

# global cleanups required on Lollipop (and above)
if [ "$sdkver" -ge 21 ]; then

# fix /system/lib permissions to ensure libs copied via symlink are correct
mount -o remount,rw /system;
chown root.root /system/lib/*.so;
chmod 644 /system/lib/*.so;
mount -o remount,ro /system;

fi;

echo -e "\n---\n" >> $log;

In my testing, I've noted that the whole annoying issue of the APK still remaining in /data/app is only with AOSP Lollipop and ROMs using the AOSP codebase; Nexus devices on Lollipop or Marshmallow still clean up after themselves as part of the optimization process. Not sure if this is AOSP being ahead of the curve, or having added something Google doesn't agree with, but I believe I've worked around it above.

How this ended up working on my test device with Lollipop (my trusty old Galaxy Nexus) is the system only seems to process 5-6 apps for optimization per boot after they have all been integrated and changes made to packages.xml. I have no idea why this is, but it gets the job done. Despite having sed remove the <updated-package> entry to trigger the process, it still remains somehow until after the system optimizes the APK, so there is still a /system APK name to read from packages.xml until that point. I mark each package that has been integrated so that once the /system APK name isn't in packages.xml, having been optimized, it knows it's also safe to delete the corresponding /data/app directory. This happens on the following boot after the one where the optimization took place. So, with a big list of APKs multiple reboots might be necessary to complete the process the first time, but then going forward it should be pretty seamless; things will get integrated and the /data reclaimed. Pre-Lollipop everything is still 100% seamless, and all gets processed at once similar to following an OTA. :good:

The script is available for download in the OPs. Put it in init.d or su.d to have it execute on early boot (recommended). Marshmallow support is untested currently, but it's visibly not a drastic change over Lollipop, so I've left it in. Still to come are APK lib removal and zipaligning for pre-Marshmallow, as well as a free space check, but they aren't a priority since it works well for a power user as-is.

Sooo are GApps obsolete now? Not quite, on a custom ROM you'd still need to have an initial GApps installation to get things started on the /system partition (then you could set-and-forget using the script), but on an end-of-life Nexus device this could be just the ticket if you don't want to switch from stock ROM but want to keep your GApps up-to-date. Just remember you need a good margin of free space in /system. :cool:

In case it wasn't clear, this is still highly experimental in Lollipop+, so be aware. Thus far it works for me there but I can't predict how apps and things will behave over time, so your mileage may vary. Pre-Lollipop on the other hand is very well tested and seems stable so I don't foresee any issues on that side of things; at most a second reboot to use the newer system libs resolved any glitches I've seen.