You could set up Out of Office assistant on each mailbox to send this reply to incoming mail. Depending on the number of users, you might want to leave this up to the user (after all, it is their mail). Make sure you've enabled OOF replies to go to the Internet (if you don't know how, let me know). Leave the Exchange Server up long enough for everyone to communicate their new address.
Also, consider creating custom recipients for the new mail addresses and using the alternate recipient option to forward all mail sent to the old addresses. That way, your users get mail as it is sent while still sending out notifications that they are migrating to a new address.