Rick, at least for SFDC Contacts, their history (campaigns, opportunities, etc.) are all associated with their previous company). If you change the email address to the new company and ostensibly the Account Name to the new Account, that data will be incorrectly associated with the newAccount and that can confuse your metrics.
When a lead leaves their company, we change their Lead Status to "Gone" and this changes their revenue cycle model stage to "Bogus Info". This effectively retires the Lead / Contact record, but preserves its history that is associated with the previous company. Then when the person goes to their new company and fills out a form with their new email address and company name, we create a new Contact / Lead record associated with the new Account. We also generate a Name Duplicate created alert, so that if we didn't know that they left their previous company, we can change the Lead Status to "Gone" on the old record.
If you have too many leads changing companies frequently and your sales team can't remember that they were at a previous company, you could add a lookup field with a link to their record at their old company. You could also give them more points in their score, etc. reflecting their prior history.