Well here is a solution SendGrid + Azure!
This article is very good explain how this scenario works. It shows how to perform common programming tasks with the SendGrid email service on Windows Azure. The samples are written in C# and use the .NET API. The scenarios covered include constructing email, sending email, adding attachments, and using filters.
Here is what’s covered
Hmm but this doesn't work for Windows Phones, since MailAddress doesn't exist in the WP API
(MailAddress sender = new MailAddress(@"John Smith <firstname.lastname@example.org>");)