This blog post saved my life yesterday when I thought it would be fun to delete students while the boss is on holiday:

How do I restore a deleted Exchange 2007 user? or A funny thing happened on the way to a reconnect? at Pennic Consulting

There are two processes: using ADRestore to recover the deleted AD objects, and using Exchange 2007 to recover and connect the deleted mailboxes. Both are useful on their own.

Hope it helps somebody.