Leveling my Pallies (on a PvP server)...
With the whole cross realm zones, the Burning Crusade zones were very populated.
There was a fair bit of competition for quest mobs.
And several higher horde/alliance (90s) who basically ignored each other and ganked the toons leveling.

Probably 10-12 horde, including my five and a similar number of alliance leveling, out of Area 52 while I was there.
None of them were from my own server.

If that trend holds true, outdoor pvp is a stronger option than before.
On a PvE server, its hard to force them to pvp but you can take the three fortresses in Hellfire on the five towers in Terrokar.
On a PvP server, you'll likely find some in every zone that you can attack.