The thread at Dragonsfoot had some pretty cool ideas about magic shops that I might be stealing. I have usually not allowed them, but these guys persuaded me otherwise. (Be warned that the thread degenerates after a bit and got locked, but the first few pages are good stuff).
Ideas I liked (none of these are mine, but they are cool):
The wandering witch who buys and sells items, and just happens to show up when needed.
Temples being the place to buy healing potions.
The Apothecary Shop that sells minor potions and low-level scrolls, but nothing else.
The dimension travelling salesman who has a shop in whatever city the PCs find themselves in. He's shady, and has to move a lot.