After much head banging, I found it to be an issue with the VIEW setting in Outlook. Apparently once in a while Outlook decides not to show new messages according to the search results I found (or if my guess is right, someone clicked something they shouldn't have).
Issue was resolved by re-clicking the view settings a few times to what they should have been, and the new messages appeared in the display.
No further response from the Cox Techs is needed. Thanks!