Die Tipps von Microsoft haben nicht wirklich geholfen. Ich bin durch die
Outlook 2013 Account Einstellungen wieder gegangen:
File -> Account Settings -> (select account) -> Change
-> POP and IMAP Account Settings -> More Settings
Internet E-Mail Settings -> Advanced
Unchecked: "Mark items for deletion but do not move them automatically
Items marked for deletion will be permanently deleted when
the items in the mailbox are purged"
Checked: "Purge items when switching folders while online"
Danach scheint alles richtig zu funktionieren. Die Mails kommen jetzt praktisch
gleichzeitig auf beiden Geräten.