Alright, I've sort of figured out the issue and wanted to share what I've discovered for anyone else having this problem.
For whatever reason, any emails downloaded by Outlook 2007 before my phone receives them do NOT come in on the phone. This is despite the fact that I have my Outlook settings set to "Leave a copy of messages on the server." It's as though once Outlook receives the messages, they're marked as read in the Gmail account. Even though they're set to stay on the server, once Outlook downloads email, messages move from the Inbox to the All Mail folder.
So the fix is simply to set Outlook to not do a schedule send/receive so I can make sure my phone has a change to receive all messages. Hope this helps someone else.