Unity 2.3 permanantly deletes messages over the phone and there's no way to get them back. You can turn on a registry setting to have us prompt with an "are you sure?" question every time you delete something, which most folks find annoying so it's off by default.
Unity 2.4 (releasing soon) will have an option on the Class of Service that lets you have messaged deleted over the phone coppied to the deleted items folder.
for voice mail only users, however, you'll want to be careful with this since items in your deleted folder still count against your inbox size, of course. There's no way as yet to clean up your deleted items over the phone so if you have deleted messages coppied and the user has no desktop access to their inbox, it will eventually fill up and they will not be able to send or receive messages.
Jeff Lindborg
Unity Product Architect
Active Voice Corp
jlindborg@activevoice.com