You could user the virtusertable to do this. Just enter a line similar to this:
user@old-address.com sameuser@new-address.com
If you do not have one already, it is a simple text file. However, you will need to build the database file that sendmail uses. To do this, just execute the following command:
makemap hash /etc/mail/virtusertable.db < /etc/mail/virtusertable
You may have to change the path to whatever your system uses.