http://www.telekoncept.se/ (hemsidan är gräslig, men vad jag förstått så ansvarar det företaget för lunarPRO)
http://www.telefix.se/ (vet inte riktigt om de kan erbjuda röstbrevlådor)
Där har du två företag att börja med. telefix har en låg komigång-kostnad, så det kan kanske vara något att testa under utvecklingstiden?
Ev. kanske du kan lösa inspelning och uppspelning på din egen server, och bara se till att få betalnummren pekade dit.
http://sourceforge.net/projects/asterisk/
kan kanske vara intressant mjukvara?