How can I sync email automatically without removing local messages that have been deleted on the server?
The behavior you described is what I'd expect from an account that uses both IMAP and POP protocols. Your emails are deleted from the server when you open Outlook and sync over POP but when you sync your phone over IMAP it keeps the mails on the server. 

You can get the desired behavior by switching your outlook sync protocol to IMAP. This keeps the emails on server and you have to manually delete them. Also, you should check out k-9 mail, it's a better replacement for the stock email app.