Mail can't delete old email address I recently picked up a used Macbook Pro with Lion installed.

There are no other accounts in the native Mail app except my new Gmail one.  

However, when I send an email, the "Reply-to" address that the recipient sees is the email address of the previous owner.  

I cannot find a way to remove this email address, it is not in the settings of my sole Gmail account.  It seems to be registered somewhere in the account info of the Mac.
Check the "me" card.  Open Address Book, go to the "Card" menu, and select "Go to my card".  Edit if required.  Restart Mail, and send yourself a test email.  Check the from address.

Also, I know you've already checked this, but please check again. In Mail.app, go to Preferences, Accounts, and make sure that the email address is set correctly.