I am in a somewhat similar situation. Here in Canada, on the Rogers network at least, we have to pay extra per month for the option of voicemail.
I would like an app that will answer incoming calls like voicemail.
Google Voice is not an option, as they don't have canadian numbers.
I know there are apps in the market that rely on redirecting incoming unanswered calls to another number for the service in question, but this can also lead to longdistance charges or use of minutes.
So really, I need an app that will answer the call on my phone, instead of redirecting it, play a message, and then record the message from the callers, and then alert me that the message is there.