Auf der Suche nach Speicherplatz ist mir das Verzeichnis /sdcard/Android/data aufgefallen, in dem offenbar die Pakete ebenfalls Daten ablegen. Einige der dort aufgeführten Pakete hatte ich schon gar nicht mehr installiert und daher konnten die Daten auch weg. Hier der nette Befehl dazu, den man vom Computer (nicht Handy) aus ausführen muss:

adb shell "cd /sdcard/Android/data && rm -ri "$(\
  diff <(adb shell pm list packages |cut -d: -f2 |sort) \
    <(adb shell ls /sdcard/Android/data |sort) \
  |sed '/^+/!d; /^+++/d; s/^+//')