Ugh, sorry to hear that.
Sounds like Outlook was in "live web" mode and all your email was on the server only, never DLed.
As the lines blur between what is on your machine and what is on the web (or the "Cloud" soon) it's going to be more and more confusing as to where your data REALLY is.
I hope that in the future there would be more of an indication that X is stored locally and Y is stored on someone's server. But I expect this kind of thing to become more and more common (and more important to watch out for) as we get hit by all the grand new ideas about web enabled everything in the near future