I know this probably wouldn't be possible unless your phone was jailbroken...but I would like to have a voice recorder that could record phone calls and store them on the phone. I would love to record all the horrible customer service people that I have talked to that give bad service (AT&T Premier...cough)
I'd love to see an app that sends certain callers or groups straight to voicemail. It would perfect for when I want to receive calls from my friends and family, but not from work.
I had something like this on my treo a couple of years ago. It also had the ability to prevent whole groups of people from getting through OR leaving voicemail.