I got down to 23mb of free space once and without losing any apps I gained about 20mb back.
Open Astro - free from the Market
menukey
tools
application manager/backup
backup all apps
uninstalled all apps except Astro (Stupid me uninstalled Astro, so I had to go reinstall it to continue)
from the backed up apps column - reinstalled all apps
This ends up moving all the apk install information over to the card, saving that amount of space on the phone itself.