CAN-SPAM Automatic Reply with new email address?

Hi Jason, personally I would not input those into my database.  They have technically NOT opted in with the new email address and therefore in violation of the law.  Or at least that is my interpretation of how this situation would work.

Hello Travis, thanks for the reply!  We plan to mark them as invalid.

I'll give the counterpoint.

First, by law, you are not non-compliant with US CAN SPAM if you simply go ahead and update the email address. 

CAN SPAM does not require any sort of opt in. It requires you to include an opt-out mechanism and a physical address of your location, requires you to obey opt out requests, requires your subject lines not be deceptive, labeling of adult content, and several other prohibitions. Read more here:
http://en.wikipedia.org/wiki/CAN-SPAM_Act_of_2003

There may be other good reasons to remove them from your database.  However, continuing to mail the updated email address would be permissible under the law. 

BTW, Canada is another story.  Much stronger laws.
http://www.crtc.gc.ca/eng/casl-lcap.htm

I would say before marking them invalid, you might create an "address change" campaign and send an email saying that "we received an automated change of address message for your email--because you had previously requested updates from us, please let us know if you want us to continue to send messages to your new address"