If you don't have SBS, see TelcomFax.

If your users always used the Exchange Address Book, this wouldn't happen.

To clear the last recipient information, use regedt32 to navigate to:

HKEY_CURRENT_USER\Software\Microsoft\Fax\UserInfo

Double-click on LastRecipientName and clear it. Do the same for LastRecipientNumber.

If you have Windows NT clients, you may select the UserInfo key and use Security / Permissions to grant the user only Read. This will prevent all Values from being changed.