What Johnatan said is the way you should do this. In the Menu step where the caller dials the menu option for leave the voice mail you have to query the Unity DB. The database is UnityDB, the table you should query is Subscriber, so you need the XferString field (extension) of the subscriber. If the query returns 0 the person doesn't have a mailbox if the query returns 1 the person does have a mailbox in the Unity System.
Considering that the Enhanced license does not include any subsystem that lets you work with another server (HTTP for XML or database for ODBC) the answer would be no.