Recently deleted mails keeps showing up in my phone (Lumia 920). It doesn't matter if the mail is deleted via Outlook.com or via the phone. What's going on, deleted mails won't be fully discarded until NSA have had time to process them? ;o)