To the best of my knowledge, such a thing requires the unified messaging system. There is a base cost, and then it is pretty much so much per seat once you get the system. I had the budget request in for this year, and put it in again for next year, but it has not happened yet so I don't know that much about it.
That's probably not what you want to hear, but the phonemail box is older than my grandma and most of them are still running on 386 processors. Unless someone on the outside wrote some custom software to do that I think you would have to look into the expressions system. The nice thing about that is it can take care of your faxes, voicemail, and everything!