Is it possible to free up phone storage while keeping HTC Sense?
I also have the safe device and had faced the same problem. I have two wonderful solutions:

1) Use link2sd. This app moves your app's apk, lib and dex file to second partition of you SD card. It will leave only the data files in the internal memory. So you can install nearly five times the more apps. I have a blog post if you want to try it out.

2) Use sueprnova ROM. This ROM is the stock ROM with data2sd support. So you can even use 2GB of SD space as internal memory.

Both of this solution requires you to have a better class of SD Card.