Even after rooting my HTC Desire and putting on CM7.1, I was still running out of space far too quickly, so I decided to try S2E (Market Link) to see if that helped.
I partitioned my SD card using Clockwork Recovery and gave myself 1GB of extra space - I then installed S2E on my phone and went for the reboot. Ideally I'd have moved all the apps I had to the phone first as this would have saved some re-installation, but I was out of room.
The first boot took way longer (it has to build a new Dalvik cache I think), but once running, everything seemed fine. I saw no speed degradation and had *loads* of space.
I'll report back on how things go...