How's this?
Blood Raven
Blood Ravens are harbingers of the judgement of Wee Jas. Sometimes Wee Jas will answer the prayers of her faithful for help against the forces of Chaos by providing a small group of Blood Ravens to act as scout or even mounts of her faithful. They appear like giant Ravens except their black coloring has crimson highlights. In rare instances a Blood Raven may be willing to become the mount of a particularly Lawful Paladin of Wee Jas,though the Paladin in question must treat the Blood Raven with respect it is due, it will in turn serve him fayjfully and bond to him as a proper Paladin Mount, including gaining all the special mount abilities.
Large Magical Beast
Hit Dice: 4d10+4 (26 hp)
Initiative: +3 (Dex)
Speed: 10 ft., fly 70 ft. (average)
AC: 15 (-1 size, +3 Dex, +3 natural)
Attacks: 2 claws +7 melee, bite +2 melee
Damage: Claw 1d6+4, bite 1d8+2
Face/Reach: 5 ft. by 5 ft./5 ft.
Special Qualities: Superior low-light vision, Circle of Protection from Chaos, Detect Chaos
Saves: Fort +5, Ref +7, Will +3
Abilities: Str 18, Dex 17, Con 12, Int 10, Wis 14, Cha 10
Skills: Knowledge (nature) +6, Listen +16, Move Silently +9*,
Spot +10*
Feats: Alertness
Climate/Terrain: Any forest, hill, mountains and plains
Organization: Solitary, pair, or company (2-5)
Challenge Rating: 4
Treasure: None
Alignment: Usually Lawful Neutral
Advancement: 5-8 HD (Huge); 9-12 HD (Gargantuan)
Blood Ravens speak Common and Sylvan.
Combat
A Blood Raven attacks by gliding silently just a few feet above its prey and plunging to strike when directly overhead.
Superior Low-Light Vision (Ex): A Blood Raven can see five times as far as a human can in dim light.
Skills: Blood Ravens receive a +8 racial bonus to Listen checks. *They also receive a +4 racial bonus to Spot checks in dusk and darkness; when in flight, they gain a +8 bonus to Move Silently checks.
Training a Blood Raven
Training a Blood Raven as an aerial mount requires a successful Handle Animal check (DC 28 for a young creature, or DC 33 for an adult) and that the creature be willing.
Blood Raven eggs are worth 4,500 gp apiece on the open market, while chicks are worth 7,000 gp each. Professional trainers charge 1,000 gp to rear or train a Blood Raven, and riding one requires an exotic saddle. A Blood Raven can fight while carrying a rider, but the rider cannot also attack unless he or she succeeds at a Ride check.
Carrying Capacity: A light load for a Blood Raven is up to 300 pounds; a medium load, 301-600 pounds; and a heavy load, 601-900 pounds.
I created this creature using a Giant Owl from the SRD as the template. Should do quite nicely as a fling mount for your Paladin, no?
