This I think it could be dificult, bassically because the throughtput of each server which send this email will detect on its rules like a spam. The only solution i have in this way only are mention on a message on each registration form in the social network, and after some correcting end-user on its client mailer will probably correct it..
Flush the cache of your site in the admin backend. Changes in language files will only take effect afterwards.
But I don't think that changing the message included in the verification emails will help you much. It will be the same message text again for all validation emails even if it is different from the original text.
What you need to do is to improve the credibility of your mailserver. You can achieve that for example by creating a valid SPF record for your mailserver, using DomainKeys/DKIM and letting your webhoster create a valid PTR record for reverse DNS queries. All these methods will help the email providers to verify that the emails sent from your domain are valid and no spam. If your webspace is using CPanel for administration you should be able to create a SPF record and configure DKIM. If in doubt, ask the support of your hoster. For the PTR record you will most likely need to ask the hoster anyway as you might not be able to configure that yourself.
You might also want to check if you IP/domain is already blacklisted. If this is the case, the emails sent will not be delivered - and most likely almost all larger email providers will block your server from sending pretty soon as they all check quite the same blacklists. Visit http://www.Spamhaus.org and http://cbl.abuseat.org and check your IP address and domain name. If there is a record, you should be able to remove it. But you would surely need to use some of the methods for giving your mailserver a better credibility or you will end up on the blacklist again pretty soon.