Assuming it's possible to transfer characters from a PvE to a PvP server (I really don't know the answer on this), that's what I would suggest you do with your Mage.

If you enjoy PvP, and can handle being a glass cannon, I'm fairly sure being a Mage in PvP is, like, the greatest thing ever. When I think of my fondest WoW memories, at least 3 of them deal with being jumped by 2 rogues in World PvP and smoking them both...or something along those lines. Those things just aren't possible on PvE.

Snape a character transfer would be the answer to all my issues, for sure. However it is not possible at this time to transfer from PvE to PvP.

The first day I started playing WoW the default server was Windrunner, I knew nothing of Realm types at the time, it's my first MMORPG and just went with with the server assigned along with some RL friends.
Six months later I discovered the joy of a PvP server and now I find it hard to go back there regardless of how much I love playing the Mage.
I can see myself eventually just building another Mage on my PvP server, a character transfer would solve that but I do not believe that opportunity will ever exist.

Ok, just bite the bullet and power-level a Mage on the PvP server. Depending on the amount of time you have to play the game, leveling a Mage quickly is very easy, in fact, it can be one of the fastest, and there are many guides on how to do it. It "can" be done in 1 week, but that's pretty hardcore, an excellent pace would still be 2 weeks, but even a casual can do it in 3 weeks if you really work at it.

Link incoming to Mage grinding guide from 1-60. Here it is: http://www.wowguru.com/guides/mage-grinding.php

Thanks Snape, 3 weeks to lev 60 thats amazing to me considering I have been playing since day one and my highest characters are 56 and 55.
I will definitely check out your link when I get home.

Well, it truly depends on how much time you have to play. That guy got to lvl 60 on a Mage in 1 week's RL time. Fura did something similar (I think it was 8 days) in Curse because he had the entire guild helping him. Of course, those are extreme cases (the author of the article probably had very little outside life), but it's illustrative of how fast things CAN happen. I think you could most definitely do it in 3 weeks if you have about 6 hours a day to play.

Regarding the fastest leveling, I believe that was done by a horde BM hunter in about 4 days /played time. I forgot the name, but it was a troll with a cat pet.

The secret to fast leveling is to do all the quests in a zone at the same time (to minimize running back and forth to NPCs) and to skip all PvP stuff until 60. It helps to have done it before, or to read a guide. Mages have a bonus that they can AE grind, but I think quest xp is more efficient (especially before you can get the good frost talents to get ice barrier)

Also if you could wait, you could take a 10 day break after using all your rested xp bar to get it full again.

It gets easier to level in terms of time every time you level a character, although it can get more boring =/

And that hunter who did it in /played 4 days... well that is the current (thus far undisputed) record for a new character on a new server... but he did it over a few weeks. And that dude is known for doing speed runs in many other games.