If there is a field in the User Profile that you're not using (e.g., 'fax', 'website', or 'photo', you could store the 'lastSent' value there.
I would store it as a Unix timestamp.
It should be possible to use a single query that would retrieve profiles with a 'lastSent' value that's more than 5 years old. If the query results are not empty, you could then cycle through them, send the email, reset the 'lastSent' value, save the profile, and send the email.
The reference point would be:
$t = strtotime('-5 years');
Your query would look for profiles where the field you use is < $t.
You could use the MandrillX class to send the emails via Mandrill and periodically check at Mandrill to see if any of them bounced.
You could put the code in a file and set a cron job to run it once a day, once a week, or whatever is appropriate.