Just got my new Desire last month on an upgrade i.e. new 24 month contract, just found out today that they have started to charge for picking up Voicemail (i wasnt told this at the renewal of contract time). So they have refunded me this month as a one off and then suggested there £2.50 month voicemail booster (unlimited voicemail pickup), which i declined.
So hunted around and found this http://www.hullomail.com/uk/ now installed and tested (checked my online t-mobile billing) to see the pick ups are actually from the call allowance so not "charged". It seems to have some neat extras as well.

It also works on iphone blackberry etc so worth checking out.