I also run a Mac Pro from early 2009. It is a double quad-core Xeon with 16GB RAM and a Radeon HD5870 with 1GB RAM. It runs 5 WoWs flawlessly, including the main with all possible eye-candies on (I dynamically reduce settings when switching characters).

I think more RAM and a better graphic card would solve your issues. The HD5870 is available directly from Apple. But you could also keep your existing card for the Mac OS X side, and install something non-compatible but more powerful that would be used only in Windows to play.