I have to admit, I'd never given a second thought to the origin of the use of "contoso". Contoso is one of a handful of domain names used in many Microsoft demonstrations. One question asked me this morning was where the name came from, with a suggestion that it was possibly an anagram (but of what, I'm not sure).
After struggling to find anything on the Internet, I figured throwing this out to the wider Internet may yield a result. You never know. I have found that the name dates back to at least 1996 though (the days of good-old NT4).