I have a confession: I love Lady GaGa. I love pop music in the vein of her style, and I'd love to hear it produced as metal.
I know, or think, there is some band that did covers of a ton of pop songs as metal, but the name of them isn't coming to me. I would prefer the covers to have some form of keyboards, but they aren't required.

Notables:
Mad World by Zonaria: https://www.youtube.com/watch?v=e-3JxAj1Mtc
Tank by The Meads of Asphodel: No video exists. :/
Lady in Black by Ensiferum: https://www.youtube.com/watch?v=W5cQdo8n0AI
La Isla Bonita by Twilight Guardians: https://www.youtube.com/watch?v=qToq_VQ8cN0

Some songs I'm looking for in particular (They don't even have to be metal covers):
One by Johnny Cash (I know he covered it too, cba to remember original artist)
Dancer in the Dark by Lady GaGa
Bad Romance by Lady GaGa
Horse with no name by America
It's the End of the World as we Know it by R.E.M.

Judas Priest covering Diamonds and Rust is pretty much the best thing ever.

How's Children of Bodom covering Britney Spears?

Are you thinking of Ten Masked Men?

You need to check out Black Ingvars, swedish coverband who've covered everything from children's songs to radio hits.

seconding ten masked men.
anybody remember that I'm blue song by that Italian europop band Eifel 65? you do now...http://www.youtube.com/watch?v=nXvQ94Z1oDM

Pathfinder covered Moonlight Shadow, Graveworm covered I Need A Hero and Losing My Religion iirc. None of these are particulary interesting (also, referring to these bands' music outside of covers), but shall fit your request. Can't recall any others atm.

http://www.youtube.com/watch?v=yfukZyVi9Hk
Taint a cover but I think it sounds infinitely better than the original.
There's one with "Bleed" too.

Michael Jackson covers, anyone?

Danish death metal band Grope covering Bjork's "Army of Me".

http://www.youtube.com/watch?v=xcNMAl48c_o

All the 60s-70s stuff Type O Negative covered. Summer Breeze (on Bloody Kisses), Cinnamon Girl (on October Rust), Day Tripper (on World Coming Down), their Santana medley. Great stuff!

The Danish band Gigandhi did a cover of Madonna's Justify My Love.

Badass song. It takes on a whole new meaning.

There are a lot of Euro-power metal bands and neoclassical artists that cover pop songs. But that really isn't very different from the original as they are pop music essentially so I have mostly avoided those.

Gamma Ray - It's a Sin (Pet Shop boys cover)
German power/speed metal
https://www.youtube.com/watch?v=IsfHFy30CuM

Lawnmower Deth - Kids in America (Kim Wilde cover)
Lawnmower Deth is a British crossover band
http://www.youtube.com/watch?v=iJz6_PEu6Iw

Raintime - Beat It (Michael Jackson cover)
Melodic death metal
https://www.youtube.com/watch?v=sBfrpu7vBGg

Christian Ice - Whenever Wherever (Shakira cover)
Bad but funny
http://www.youtube.com/watch?v=FTEOgaYj ... ure=fvwrel

Children of Bodom - Umbrella (Rhianna cover)
I think they only did this live
http://www.youtube.com/watch?v=4JsiUthk ... re=related

Sinergy - Gimme Gimme Gimme (Abba Cover)
Symphonic metal
http://www.youtube.com/watch?v=43zqYNIvUh0

Graveworm - Losing my Religion (REM cover)
Almost forgot this one. They are gothic/black metal
http://www.youtube.com/watch?v=bZxLz_x6YMM

Graveworm - I Need a Hero (Bonnie Tyler cover, I know it from Shrek)
http://www.youtube.com/watch?v=H9-HUWx2 ... re=related

Megadeth - These Boots (Nancy Sinatra cover)
Pretty well known one. Surprised I am the first to mention it
http://www.youtube.com/watch?v=Ro8C9yx6ikY&feature=fvst

The Bezerker - All the Things She Said (T.A.T.U. cover)
cybergrind band covering those slutty Russian girls
http://www.youtube.com/watch?v=h_c25kAdmu8

Norther - Smash (Offspring cover)
CoB clones
http://www.youtube.com/watch?v=Hm3DzHOmSDs

Norther - Final Countdown (Europe cover)
Everyone knows the original, very cheesy
http://www.youtube.com/watch?v=wNvRMBqq ... ure=relmfu

Cradle of Filth - Temptation (Heaven 17 cover)
Danni's voice sucks as usual. Acquired taste I suppose.
http://www.youtube.com/watch?v=MfMa2lrFxhY

Kingdom of Death - Whenever, Wherever (Shakira again)
Very rare for black metal to cover pop, so I had to throw this one in when I found it. The riffs sound morel like black n' roll. Look out for the little AC/DC bit.
http://www.youtube.com/watch?v=P-7lLN5L ... re=related

Xentrix - Ghostbusters (Ray Parker JR for the awesome movie theme. If you dislike the movie then something is wrong with you!)
Thrash band.
http://www.youtube.com/watch?v=RtafNuya ... re=related

Bonded by Blood - Teenage Mutant Ninja Turtles theme song
Xentrix reminded me of this one by these retro-thrashers.
http://www.youtube.com/watch?v=AlfjNTqbFLA

Not sure how metal you count within temptation, but they have just done covers of:

Coldplay - paradise
bruno mars - grenade
gnarls Barkley - crazy

All are passable, even if the originals are detestable.

They also did a good cover of Kate Bush's running up that hill.

Ashes you leave did a great gothic doom cover of every me, every you by Placebo.

Not the songs you're looking for, but they might interest you:
Thy Disease - Frozen (Madonna cover): http://www.youtube.com/watch?v=NYjieb9VEZU
DevilDriver - Black Soul Choir (16 Horsepower cover): http://www.youtube.com/watch?v=NlRtG9ls3Ig I know this band isn't loved around here, but I like them and especially this cover.

Graveworm has done a couple of pop covers. Losing my Religion and I Need a Hero are mentioned already so I'll add another one:
Message in a Bottle (The Police): http://www.youtube.com/watch?v=YAnxnkFPTn8

I sense a lack of Louis Armstrong in this thread... played by Ghoul! Enjoy!

Also, ABBA covers: Gimme Gimme Gimme by Yngwie Malmsteen, and Summernight City by Therion.

Woods of Infinity covered Moonlight Shadow too, as well as Old Songs by Barry Manilow.

The Meads of Asphodel also did a cover(kinda) of Wonderful World.

Add to that Tad Morose's awesome take on "Knowing Me, Knowing You"!
http://www.youtube.com/watch?v=WAfuxaTCsOo
and of course Helloween;
http://www.youtube.com/watch?v=-9k3f4yv6Ac

Root - Strawberry Fields Forever (originally The Beatles)
http://www.youtube.com/watch?v=RWm5ABNHLH0

Melechesh - Gyroscope (Tea Party cover)

Wormrot - Rich (Yeah Yeah Yeahs cover)

Lagerstein - I'm on a Boat (The Lonely Island Cover)

As far as the songs you specifically listed, I just know this one Bad Romance song.

Cradle of Filth covered Iron maidens Hallowed be Thy name

Norther- Europe's The Final Countdown

Children of Bodom- Britney Spears- oops i did it again

This guy covered Katy Perry www.youtube.com/watch?v=vil-s82_LM0

a band called viral millennium who is industrial metal covered a lady gaga song which actually sounds really good(their cover i mean)

http://www.youtube.com/watch?v=PaDjDJiYffk

there is the cover, i love that cover and i saw it live

I lol'd that you spelled it with two "n"s (inside joke)



Also, metal covers of pop/common songs are ... pretty common and pop. Just go up on your youtube and you'll find it because people generally love gimmicks.

Samael - I Love the Dead (Alice Cooper cover)
Ensiferum - Vandraren (Nordman cover)
Sentenced - Creep (Radiohead cover)
In Blackest Velvet - Losing My Religion (R.E.M. cover)

(listed on MetalArchives...but sounds pop/rock)
RaHoWa - The Snow Fell (Skrewdriver cover)
Elvenking - Heaven is a Place on Earth (Belinda Carlisle cover)
To/Die/For - In the Heat of the Night (Bonnie Tyler cover)
To/Die/For - [I Just] Died In Your Arms (Cutting Crew cover)

OH GOD, my sides!

http://www.youtube.com/watch?v=pi00ykRg_5c

Okay, just got through all of this!

Bands I liked:
To/Die/For
DevilDriver
Thy Disease
Sinergy
Ten Masked Men

The rest of them I either knew beforehand or were indifferent/didn't like.

I should note that I love Within Temptation, Sonata Arctica, Elvenking, and Type O Negative.

Sodom - Surfin' Bird (the Trashmen)
http://www.youtube.com/watch?v=ZnYzQsZXIRc

Quo Vadis (Pol) - Venus (Shocking Blue)
http://www.youtube.com/watch?v=VagLPF_3xYw

Ghoul - Wonderful World (Louis Armstrong)
http://www.youtube.com/watch?v=8y_wJRtS6-Y

There's a few bands that have put out cover albums as well, although I think they are generally of other metal or classic rock songs. I can think of Iced Earth "Tribute to the Gods", Overkill "Coverkill" and Entombed "Sons of Satan Praise the Lord".

Dispatched did an awesome cover of Flicka Med Guld, but I can't find it online.

Hysterical!

On subject, people should know about the Black Seed Boys:
http://www.blackseedboys.de/index_english.htm
Check the Mortuary section for Mp3s.

Check out AndyRehfeld on youtube, he does some great metal covers of pop songs as well as a lot of other interesting stuff with metal songs.

I used to know another musician on youtube that did hundreds of metal covers, but I've lost track of him.

I've heard a lot of such covers but the only one that comes to my mind atm and that wasn't already mentioned is Loves Me Not (originally by Tatu) by Spasm.
https://www.youtube.com/watch?v=8X-2_YqP8rU (not best audio quality but I didn't find a better version on youtube).

And not quite pop songs but Powerglove and Megadriver are famous for covering video game music and the like:
http://www.vgmetal.com/
http://www.megadriver.com.br/

How has no one posted this classic?

Nuit Noire - Paparazzi (Lady Gaga)
http://www.youtube.com/watch?v=lBsGycxYd_E

is Lady Gaga even old enough for anything related to her to be classic yet?

Lord - On A Night Like This
Great Kylie Minogue cover, or greatest Kylie Minogue cover?
http://www.youtube.com/watch?v=A1i3cBS2kx8

quite like this version of Toto's Africa (what else?)
http://www.youtube.com/watch?v=YQb9_-wNVG8

the greatest Kylie Minogue cover is performed in a key only dogs can hear.

lol a few covers of Paparazzi out there also love the chaos divine and the lord songs