Great suggestions. I'm loving the Rock Me Amadeus and I Kissed A Girl ones.
Halestorm does great covers as well and put out a covers CD between each full album but out of the 3 they've done so far I'd say Bad Romance kicks the most ass.
My next suggestion is Danger Silent - Crystallize (Lindsey Stirling):
https://www.youtube.com/watch?v=gGE_tS-SYZQSomehow they managed to squeeze in clean male, clean female (even if it is autotuned, that's the effect they wanted I'm sure), growls, and a rap into it and it sounds like they're meant to go together.