[MENTION=6777454]TheHobgoblin[/MENTION], I understand where you are coming from, but I think there are just some things you have to accept for fantasy campaigns. If you have races that live underground (whether dwarves or drow) you have to accept that there is some way that those races can feed themselves.
I always assume there is magic involved with underground ecosystems in typical D&D campaign settings. Mosses that magically eat rock and glow that is harvested by dwarves and placed strategically to slowly enlarge caverns and to provide light for crops. I think of it similar to a long term space ship. There has to be a power source other than the sun. Is that power coming from hydrothermal vents? Magical crystals? Some combination of the two?
If you assume that you can provide light (and possibly heat), you can set up an underground greenhouse that could actually be more productive than topside because you can control all of the inputs.
Alternatively, dwarves do all of their farming above ground and simply live underground. Either way is fine, it's going to depend on how you see your world working.
Anyway, didn't mean to sideline the thread. Just stating that if you accept underground races, food supply is a secondary consideration.
Okay, I suppose that is a fair enough point.
But are you then saying that how exactly you are supposed to feed these mounts should in no way be a consideration at all? That's really the primary issue I see with so many of the suggestions here. How exactly are you feeding these things?
You shouldn't just say "we'll have basilisks" or "we'll have giant rhino" or something like that without the question of how you feed the thing coming into play. That's going to be a question for every individual who would think of having one and most certainly ought to be a consideration if you are talking about whole armies dragging these creatures around against their will.
Horses feed off of grass. And most sorts of grass are inedible to humans (wheat, corn and a few others). Thus, if your society lives on a wide open grassland and this grass is not edible to people, it makes all sorts of sense to keep around animals that can eat this grass for food, labor and transportation. Once you no longer have those wide open grasslands, they generally become more trouble than they are worth.
Giant boars, if such a creature existed, would be a potential alternative. Similarly, boars can eat all sorts of refuse that humans either can't or won't eat. That's why cultures that live in temperate or tropical reasons kept them around to feed them what humans don't get to get them big and fat and then eat them. So if you have a people who are from a tropical heavily forested climate, giant boars would work well.
Some sort of Moose or giant Reindeer would work well for a people who live a colder climate because they are good at finding food and, again, don't eat what humans prefer to eat.
And if you have a people who live in a generally uneven, mountainous region... giant goats could be a good go-to option. Although I wouldn't expect such mounts to be particularly fast-- they would just be considerably more sure-footed than a horse would be.
Goblins riding Wolves is a very difficult one to explain. Aside from the fact that no stat block for goblins has ever given them a super-human ability to tame animals as they surely must have if they can dominate primarily predatory creatures that are larger than them, it isn't clear where the food supply comes from. Sure, goblins might well be able to eat things humans would not, we are not really led to believe they can eat grass or leaves or such, and while wolves are primarily carnivorous, they can live on an semi-omnivorous diet-- but, again, no grass or leaves or such. Then again, I guess because such goblins and wolves are living in forests teeming with wildlife, they manage to get by and perhaps supplement their food supply by theft or raiding human and halfling villages or maybe even just going through the waste of large cities for discarded food sources. Plus, we are never particularly led to believe there are really whole massive regiments of wolf riders, not the way there would be regiments of human horsemen. (Sure, they were there in LotR, but not so much in D&D)
Even your suggestions of how Dwarves might be able to get enough food to feed themselves seems to at least support the idea-- they aren't going to have extra food for beasts of labor or mounts.
However, there is a possibility, I suppose. Considering we are talking about a world with magical creatures here... I suppose if we consider one can imagine up anything. In which case, if Dwarves are going to be using beasts of burden or mounts, it would sort of have to be something that can sustain itself primarily off of rock and maybe requiring heat that can either be provided by geothermal power or sunlight. Sure, such a biology wouldn't make sense (not in a creature large enough to carry a Dwarf at least) and I am not sure why a rock-eating creature with no predators and no prey would be any faster than a Dwarf... but since we are just shrugging our shoulders and saying "because magic" or "because imagination" it is imaginable even if not a rational, logical element to add into our world.
Also, the whole issue of providing a food source is really only a serious issue for the subterranean Mountain Dwarves. As I understand Hill Dwarves, they are at least primarily surface dwellers. As such, they do farming on the surface and their mountains are likely covered with grasslands. Given the conditions though, World of WarCraft's solution of giving Dwarves giant goats as mounts seems perfectly reasonable.