Regarding Microsoft support, I contacted them on Wednesday. They were actually very helpful. They remoted my laptop, checked the config of my Outlook account, and even created a second version of the account. For that second version, they waited while a full clean sync took place, and again the messages stopped at 10,000. They finally concluded that nothing in Outlook in general or my config specifically was imposing a limit, and I was convinced.
Also, regarding the Bulk Mail issue, while I agree this is not specifically an issue for this thread, I do want to clarify what happened with me, since it may help understand the overall problem with mail synchronization. For me, I had left my laptop running with Outlook open for about 3 hours. Before I left it, I could see all my emails in the inbox (about 208k messages, 48k unread). Up to that point, the AOL spam folder online was synching to a folder called "Bulk Mail". When I returned to the laptop, the 10,000 limit was now in force, and spam messages were now synching to a new "Bulk" folder. The "Bulk Mail" folder was still there (in fact a few spam messages were in it as well), but since then it has remained empty and all new spam messages are now in the "Bulk" folder. Don't know if this helps support the argument that the 10,000 limit problem is with AOL/Yahoo, but I thought it might be important to note.