Not sure what you mean by "email notification of voice mail". Unity actually stores voice mail directly in the inbox, we don't send links to the voice mail to mailboxes or the like. Yes, VMI can do something like this but that's a bit of a different issue.
Do they want to migrate to unified messaging from a voice mail only configuration? If this is what they want to do, it's doable. Unity can handle users in different domains so long as you configure your permissions properly (the permissions wizard off AnswerMonkey can help you here). The trick is to grant access on the root containers you will be importing/creating users on in AD on each domain.
the Customer Applications Team will have a migrate user tool out for 3.x here in the next couple weeks that can also help out here. You can move your Unity subscriber data off your voice mail only email accounts and onto your corporate email accounts without losing any data such as greetings, voice names, phone passwords etc... if this is the scenario you're talking about, this tool will save you a bunch of work.
Jeff Lindborg
Unity Technical Lead/Answer Monkey
Cisco Systems
lindborg@cisco.com
http://www.AnswerMonkey.net (new page for Unity support tools and scripts)