Lord of the Rings:
Hmm, I reckon so. That means that Aragorn would probably have a...hmm, I'm thinking a Shifty (he's a Ranger, therefore he must be silent and deadly) and a Arcanine (dunno, it fits).
Gandalf would have a Alakazam, and Saraun (the White) would have a Hypno. Saroman would have a Sableye (mini purple orc anyone?) and a shadow Lugia or some other dark flying dragon thing (Nazgual).
Shiftry doesn't seem to fit Aragorn that well... though Arcanine certainly does. I also Gallade better suits him than it does Legolas. (Why would an archer want to keep a swordsman anyway?) For the record, Arwen would have Gardevoir--besides, it fits, as a Gardevoir would gladly sacrifice itself for a loved one.
I think you have Sauron and Saruman mixed up. It's Sauron who commands the Nazgul, and Saruman who is (or rather, was) the White. Also, Hypno fits Saruman to a T. I also think he'd want to catch a Grumpig, thinking it wears three palantirs on its forehead/belly. Sauron would have to have nine Shadow Lugias to hold all his Ringwraiths.
I think Rapidash would suit Gandalf well. Doesn't it resemble Shadowfax? And Galadriel would have Uxie, who seems to almost be her Pokemon counterpart.
Moving out of Middle Earth, let's talk about some other characters:
Jack Sparrow could also have a Grumpig, due to the ship called the Black Pearl.
Meta Knight also gets a Gallade. It would make a great training partner. That or Scyther.
King Dedede gets a Magcargo. He'd think it's Escargoon, and citizens of Dreamland would laugh when the Magcargo Flamethrowers him for whacking it with his hammer.
And now to pick on some Harry Potter characters:
--Snape gets a Lileep. Say "Lileep" over and over again and soon you'll understand why (if you read the last book, that is).
--Lupin gets a Darkrai, since it would probably be able to protect him from full moons. He'd want to stay away from Lunatone and Cresselia, likewise.
--Dumbledore can also have a Moltres--it too looks much like a phoenix.
--Peeves gets a Misdreavus, since it loves to pull pranks just as much as he does. (However, Nearly Headless Nick would not want to go near one.)
--Umbridge gets a Skitty. Lots of them in fact. And a Purugly.
--Ron gets a Rattata, in order to replace Scabbers.
--Dobby gets a Snorunt, to add to his hat collection.