The 1/2 block of Grande whole milk that I purchased from a local pizzeria also tasted like muenster. I know exactly what you mean. I have no idea how old it was. It didn't look that gray, maybe a little grayish yellow, but nothing crazy. One thing is for sure it was nowhere the snow white that fresh, or most of the cryo pack style mozzarellas are. I remember a post on this board from someone who seemed to know what they were talking about that said that until mozzarella molds the flavor just gets better and better. Do me a favor and don't throw that block you have out. Then let us know how the two compare when the new one shows up.
I did an 8 brand high end, dry (processed) mozzarella shootout a while back. I made sure to pick up most of the brands that had won first place at Wisconsin cheese competitions. You've got to love that state! It was amazing to taste how some mozzarella was so much more sour than others. Maybe sour is the wrong word to describe it, but I don't know how else to put it. Grande was actually pretty sour (Muenster like) compared to a lot of them, but the nice thing is that it was much more creamy than anything. I think that is why it melted WAY better than anything else, and could hold up to high heat without burning better than anything else. For flavor I favored the brands that had less of a sour taste, and more of a buttery taste. Unfortunately the one with my favorite flavor is a little on the dry side and can burn if you aren't careful. I guess some people don't mind that though. If you are one of those people check out Great Lakes. The flavor is really amazing. I just have a feeling it is going to be hard to find.
Now with my supercharged oven, I pretty much have to stick to fresh mozzarella. If you are one of the people like I used to be that thinks fresh mozzarella is bland try this. Find a local manufacturer of fresh mozzarella, or find out from your grocer when they get their shipments. You might be surprised if you check the yellow pages that you have someone in the area that makes the stuff fresh a few times a week. Get it within a few days of being made or received at the store. Squeeze the ball lightly with a paper towel wrapped around it. Repeat this step until dry. Now cut thin slices and lay them out on a plate. Sprinkle a decent amount of good sea salt on the cheese, then rub it in. Flip the cheese over and repeat. Coat the cheese with some good medium priced olive oil, preferably unfiltered. Raineri is really good, and Coluccio is even better and cheaper. I used to not like fresh, but now after following these simple steps I am blown away at how much creamy buttery flavor it has. And no muenster! Maybe it is just my local cheesmaker, but the complexity of the flavor is so amazing. You taste it unsalted/oiled and it tastes like water. You add some salt and melt it (for some reason it has to melt first) and it seems like the best cheese in the world. I can't figure out why, but it works.
Also, sorry to bash Grande here, like I said nothing performs like it and it is better than 90% of the junk out there, but I know there is another dry (processed) mozzarella that is used by a handful of the best places in the NY, NJ, PA, CT area. I have been trying desperately to find out what it is. It melts like grande, and has a similar but even better flavor than the Great Lakes. I remember reading a post on one of the forums (chowhound? I can't remember). It was a guy, I think in Jersey, that was talking about his favorite pizzeria ever. Basically the story was that all of a sudden this place just went to average quality over night. Along with the change in flavor, for the worse, came the pretty wooden "We proudly use Grande cheese" plaque on the wall. If I remember correctly I got a laugh out of the story because he was talking about how the place had cut corners and started using this cheap cheese. I have a feeling nothing is more expensive than grande! Just about every foodservice distributer I have checked with says that it is in the $3.50 a pound range while the next most expensive cheese they carry is only $2.50 a pound. That's a pretty big jump in price, especially when you are buying a whole fridge full of the stuff like the busy pizzerias do.