I've written some python code to save a copy of the MXD before its exported as a PDF and I can see that the basemap isn't added to the MXD at all for some reason, even though its on and visible in the web application (tried with both Javscript and Flex APIs).
But yeah the issue only occurs when you zoom into the max scale and have a smaller screen resolution.