Automotive paint stores are usually a good bet, or you could try your local car repair guy. Remember that these fine grits are usually done by hand and not by orbital sander.
I'm surprised Wally World didn't have it. That's usually where I buy my 1500 and 2000 grit sandpaper.
Did you look in the automotive section? Thats where they usually keep the 800+ grit sandpaper. They usually keep the lower grit sandpaper in thte hardware section.
Micromesh is a more specialized sandpaper, not likely to be found in a big box store but much more often found in auto body supply or woodworking stores.