It's a year on since the original posting and I, too, find it amazing there is no 'answering machine' app to be found out there.
Here in the UK I am with provider Orange (now part of EE) because of signal issues in the area. However, they charge 36 pence everytime I dial in to voice mail. And they also charge for call forwarding (unless to another Orange number)which rules out using such services as Hullomail.
I'd even pay for such an app as clearly outlined by DarkSky.