No. I don't think they do. It wasn't generic until Apple made it so in the public's mind. That's your (and Microsoft's) problem here. Apple "owns" the combination of App and Store. It was NEVER used commercially prior to Apple using it commercially. And, unless some one can demonstrate otherwise (and so far no one here has), there was no common usage of "app store" prior to Apple's use. You just saying that's a phrase you've used before doesn't mean anything. If anything, most people used the word program, but even if we dispute that, they would have talked about buying an app, installing an app, etc., but never used app store prior to Apple's use.
You can be sure MS lawyers are trying their best to locate those two words in some close proximity in some obscure manner used to sell computer software.