I'm still having this issue, but I did discover something last week. It appears the online base maps are downloaded as a .lyr files when you access them from the ESRI service. I found .lyr files for each of the "online basemaps" I had accessed in the past in the "My Documents" folder...
C:\Documents and Settings\***username***\My Documents\ArcGIS\Packages
Now I can simply drag the basemap .lyr file into my map. For example, let�??s say I want the Bing Aerial photo back drop I had accessed via the online basemaps a few months ago. I browse to this directory above and find a folder called "Bing_Maps_Aerial.lpk1". I double click and open this folder to find the basemap .lyr file called "0000Basemap.lyr". Simply drag the .lyr file into your maps Table of Contents and your map will then downlaod and display the information.
Once I figured this out, I relocated these .lyr files to a directory where I store my other basemap .shp files so I can easily drag it into future maps.
It�??s not a fix, but it�??s a work-around that works for me. I hope it will help you all out too.
...Also, I've not tried this yet, but I wonder if clearing the "Display Cache" folder will fix this? I should test it before posting this, but I'm out of time and got to go and I don't want to spend time trouble shooting if it screws something up right now... Its located under "Customize" drop down window, then go to "ArcMap Options", then choose "Display Cache" tab.