Artists who have released alternate versions of songs.

Little Feat re-recorded "Willin'", originally on their eponymous debut album, for their second album "Sailin' Shoes".
Slightly less on-topic, they also re-recorded "Cold, Cold, Cold" and "Tripe Face Boogie" (both on "Sailin' Shoes") as a medley on "Feats Don't Fail Me Now".
Albert Hammond's early discography is littered with this sort of thing, for example his (excellent) eponymous third album features remakes of "Everything I Want To Do" and "Names, Tags, Numbers And Labels", originally on his second and first albums respectively.

 

In January 1969, Peter Green's Fleetwood Mac and Otis Spann recorded a version of "Temperature Is Rising (98.8°F)" as a single B-side, and another for the album "The Biggest Thing since Colossus" entitled "Temperature Is Rising (100.2°F)" - as the title suggest, the latter is really thwe hotter version.

Paul Rodgers recorded LIVE IN PEACE for his 1983 solo album CUT LOOSE, and re-recorded it with Jimmy Page & Firm for their first album in 1984. Got him in big trouble with Atlantic Ahmed but somehow he & Pagey got away with it...

In 1986, EC rerecorded AFTER MIDNIGHT (which first appeared on his first solo album in 1970) for a beer commercial. Humm, if I'm not mistaken, most fans find the new take unnecessary and ...well, lukewarm (to find a term fitting for the connection with beer) .

 

Joni Mitchell - Travelogue, a double album of alternate (orchestral) versions of her songs. A very good album actually.

 

Bowie again: 2 versions of 'Rebel Rebel' (UK version, American version).

 

Dire Straits recorded "Sultans of Swing" three times. The first was their demo, which was played on Charlie Gillett's BBC radio show and appears on a couple of UK compilations. The second was the familiar LP version, which was also the hit single in the US. The third was a less polished, more or less live-in-the-studio version that was recorded for the single. In the UK, this version is on the Vertigo 45; in the US, this version made it to some promo 45s and 12-inchers, but Warner Bros. pulled the promo and replaced it with the LP version.

The Ventures recorded "Walk...Don't Run" twice. The second one was called "Walk...Don't Run '64" and was a hit in its own right.
The Beatles did "One After 909" twice, once in 1963 (left in the can at the time) and again in 1969.
The Miracles recorded "Shop Around" twice, within days of each other in 1960. The first version was pulled in favor of the second, which became the hit.
The Carpenters recorded "Ticket to Ride" twice (1969, 1973), "Merry Christmas Darling" twice (1970, 1978) and "Santa Claus Is Coming to Town" twice (1974, 1978).

Pop vocalists often recorded songs more than once for release:
Frank Sinatra recorded and released two, three or even four versions of more than 100 songs.
Dean Martin's hit version of "Everybody Loves Somebody" is a re-recording of a song he first released as an LP cut earlier in 1964.
Nat King Cole recorded four studio versions of "The Christmas Song," each different in its own way.
Bing Crosby released two studio versions of "White Christmas," in 1942 and 1947, the latter after the original master had worn out.
Harry Belafonte recorded "Jamaica Farewell" twice, once for the album Calypso and the other for 45 release. The album version has backing vocals on the choruses.

 

Manic Street Preachers - You Love Us

Originally released as a single on Heavenly Records, then re-recorded a few months later, without the Lust For Life ending, for the Generation Terrorists album.

 

Big Star - In The Street - album version and Big Star - In The Street - single version. Both different recordings!

 

Half of Donovan's Lady of the Stars album consisted of re-recordings (he also re-recorded the songs from Brother Sun, Sister Moon).

 

Look at all the bands from the late 70's to early 80's and their extended mixes...lots of tracks were re-recorded.

 

They're two different songs but with two lines in common.

John Martyn recorded "Couldn't Love You More" for One World and then again for Glorious Fool.

 

Pink Floyd, or rather David Gilmour, re-recorded Money for A Collection Of Great Dance Songs.

Something to do with Capitol Records refusing to licence the original.

 

John Denver -Leavin on a Jet Plane (a compilation I have has both)
Todd Rundgren - did Hello It's Me with The Nazz and then solo (the latter was the hit)
Todd Rundgren then did an album of re-recordings Bossa Nova style, called "With a Twist"

 

The Beach Boys did a boatload of re-recordings, many of which (like "Help Me Rhonda") are superior to the originals and some of which are not.

 

Saxon re-recorded a bunch of their songs for the comp Heavy Metal Thunder. Basically letting the new line-up put down more aggressive, better recorded versions of some of their best songs.

 

Bowie-Space Oddity '79

 

Herman's Hermits recorded the single of "Hold On" and "Leaning On the Lamppost", then on the Hold On soundtrack album, both songs appeared in re-recorded versions. On all the Greatest Hits comps I've heard, the soundtrack album versions were used, although the single versions are much better.

Also, the Police did a slow version of "Don't Stand So Close To Me" (unfortunately).
John Coltrane recorded 2 takes of Ascension, both of which are included on the superb The Major Works of John Coltrane.

 

It probably doesn't count because of the language thing, but:

Sie Liebt Dich
Komm, Gib Mir Diene Hand

 

The Pretenders released a version of "The Wait" as a b-side to "Stop Your Sobbing" in Jan. 79 that is a different recording to the one on the debut LP.

 

This is probably splitting hairs a bit, but the mono 45 version of The Grateful Dead's "Truckin" has a completely different lead guitar track by Jerry Garcia. It is obvious.

 

The Rolling Stones did two very different versions of "Time Is On My Side." The first released version, and the hit single from late 1964, is the one with the four-note organ intro and the ending that fades. The second released version, recorded in 1964 but not issued until 1966, is the one with the guitar intro and cold ending.

Tommy Edwards recorded "It's All in the Game" twice, in 1951 and 1958. The 1958 version was recorded when he was doing a stereo album for MGM consisting of new recordings of his early-1950s hits, and that version became a huge #1 hit.

 

Buckingham-Nicks rerecorded Crystal on Fleetwood Mac's S/T.

 

The Rolling Stones
Everybody Need Somebody To Love

The Animals
We Gotta Get out of This Place

Both of these had different/incorrect US versions than their UK counterparts.
To me, the UK version of "Everybody Need Somebody To Love " on "The Rolling Stones No.2" is superior to the one found on ''The Rolling Stones Now"
But the US version of "We Gotta Get out of This Place" beats the UK one.

 

The Breeders released the song 'Saints' on their 'Last Splash' album, and another version in a different key on the 'Head to Toe' EP.

There's also 'Behind The Lines' by Genesis on 'Duke' and on Phil Collins' 'Face Value' Album.

 

The single version of Everyone's Agreed That Everything Will Turn Out Fine by Stealers Wheel is very different from the album version. The titles are also slightly different but the song is the same.

 

Paul McCartney has tons of different versions of No More Lonely Nights. Most of which are pretty hard to find.