What type of email server are you connecting to with Outlook? Is it Exchange, POP or IMAP?
Sounds like your Outlook may be connecting to your mail server using POP, which will remove the messages from the server, so when your phone goes to check for new messages, they aren't on the server.
Some hosts don't support IMAP connections, but if yours does, this would be the better way to set up your connection from Outlook.