Arthur: Ah, the ol' we won't sell enough-- amazing, considering that the cheese dept here said that this mozz moves incredibly well, and Whole Foods in general prides themselves on carrying cheeses from top vendors. If Grande is on your store's list (a booklet that the grocer and other departments hold at each Whole Foods) as an accepted vendor though, than they have to be willing to do a special order for you. The list varies by store though.
Regarding other cheeses recommended above, I've tried many of the cheeses mentioned, including fontina, asiago, provolone and smoked provolone. Certain toppings like aged pecorino and dried goat's cheese is something I use daily. I used to mix with fontina or asiago, until I found EDAM. Pyzano's pizzeria uses a mixture of provolone with Grande mozz and the pizza I tried was very good; but I have not had the same success when I try it myself. Most of the time, I use Grande by itself and always add a dry pecorino at the end. EDAM has worked as a tasty dry cheese to mix in small amounts with it.
I have not tried Pierre's suggestion though; Gouda sounds like a good alternative. Pierre: have certain manufacturers been better than others with the Gouda?