In Elder Evils, there is a bodak blackguard who has a really cool mount. It's a flying construct with a nightwing's essence bonded to it. Very reminiscent (perhaps borderline steal?) of the Hobgoblin. Needless to say, one of my PCs asked if he could have a wyvern at a sufficiently high level instead of an ill-tempered pony.
Are there any rule precedents for blackguards or paladins having alternate monstrous mounts? I'm most interested in published variant rules (if any). Short of those I'll take any reasonable suggestion. So far I've just been treating them like additional party members, such as cohorts gained from the leadership feat. Is this the only choice available to DMs, currently?