A prototype instrumental of Seven Seas of Rhye rounds off Queen's debut. The full version turns up on Queen 2.
There must be more but I can't think of any.

Versions on 'The Freewheelin' Bob Dylan' and 'Nashville Skyline'. The latter, admittedly, as a duet with Johnny Cash.

Also the two versions (single and White Album) of Revolution, though this doesn't adhere strictly to your criterion of being on two different albums.

appeared on the debut album then was re-arranged and re-recorded on Works Volume 1

'Europa and the Pirate Twins' on 'The Golden Age of Wireless' LP, then many years later - 'Eastern Bloc' on 'Astronauts and Heretics' LP.

The new Costello record has a redo of Complicated Shadows, last heard on his 1996 Attractions record All This Useless Beauty. Both different, both good.

The two fabs versions of One After 909 are interesting to compare, even though the original wasn't released until the Anthologies.

Don't Cry is on both Use Your Illusion 1 and 2. On 2, it's a version with alternate lyrics.

Voodoo Child (Slight Return); although they were both on Electrif Ladyland.

were definite proponents of this:
Willin' appears on their 2nd and 3rd albums, Cold cold cold on their 2nd and 4th,exactly like Tripe face boogie.

wasn't there a version on EVERY album they did?

does her song "I Drink" on her albums 'Drag Queens In Limousines' and 'Mercy Now'. Same song though both are very slightly different.

Steve Earle, on his 'The Revolution Starts... Now' album has the first song called "The Revolution Starts" and the last song called "The Revolution Starts... Now". The same song twice! The only difference is a little coda on the second one. Talk about filler!

performed by everyone from Chris Rea, "New light thru' old windows" and, slight nervous cough, Mick Hucknall with the Simply Red hits back catalogue. This concept also occurs as the live greatest hits LP that many have done.
On this track, how annoying is a greatest hits package that proclaims to have "all the hits" which turn out to be all the ones on that record label, with the rest in dodgy live mode......?

New York's Swans adopted a scorched earth policy to the re-release of their back catalogue. Entire albums were wiped from history and replaced with compilations which selectively documented the middle period of the band's career.

This revisionist mindset was occasionally applied to individual songs: The penultimate Swans album - the German-language Die Tür Ist Zu - opens with a 21 minute monster called Ligeti's Breath/Hilflos Kind, which is as hard going as the title suggests. A shorter English-language version of this track, christened Helpless Child, later appeared on the band's swansong Soundtracks for the Blind.

A similar thing happened to Where Does a Body End?, which in its original form on The Great Annihilator, is a set of lyrics undermined by a chugging, one-note tune that races ahead of the words, as if voluntarily labelling itself as filler.

A better version of the song, retitled Where Does Your Body Begin? appears on Michael Gira's solo album - Drainland. Here the unsettling images of asphyxiated bodies floating in a river, and mass-telepathy eroding personal identity, are held in near stasis by a cosmic, ambient score that gives the lyrics room to breath and time to sublimate into your consciousness.

Strangers When We Meet was on the soundtrack to The Buddha Of Suburbia and on his next album, 1.Outside. I'm guessing he included it on the latter because the former was a very low seller and he thought a song that good deserved a second chance. That's what I think anyway.

Virginia Astley's piece A Summer Long Since Passed appears on at least two of her albums, possibly three.

In a rather odd variation on this theme, there are two songs on Carmel's album World's Gone Crazy which are lyrically identical to older songs, just with different tunes.

"Couldn't Love You More" is on "One World" and then recorded again for "Glorious Fool" a few years later. Bonus points for "No Little Boy" where he re-recorded a load of his old stuff.

Recorded by Dylan in two different versions, both on the Planet Waves LP....

Mothers of the Disappeared is the backing track to One Tree Hill slowed down and treated by Eno.

Neil Young
began and ended Tonights the night with the Title cut. Sort of did the same with Rust never sleeps (Hey hey My My (Out of the Blue)(Into the black)Acoustic vs electric

But I finding myself posting the answer "Steely Dan" in two consecutive posts (see also my suggestion for Liddle-baiting cover stars).

Anyway, in this context 'The Dan' released 'Your Gold Teeth' on Countdown to Ecstasy' and "Your Gold Teeth II' on 'Katy Lied'. They seem to be pretty different songs though, different key, arrangement and mostly different lyrics other than the central trope of throwing out one's gold teeth and seeing how they roll.

And pretty much every Jonathan Richman album since Modern Lovers features a re-recorded version of earlier works: one example - 'Affection' features on both 'Back in Your Life' and 'I'm So Confused'

...a few versions of Careful With That Axe Eugene, under different names, around? No? I'll hand in my Cosmic Scousers card...

You Me Us has several tracks in electric and accoustic mode:"Voltage Enhanced" and "Nude" as the 2 separate CDs put it. Possibly his worst LP, IMHO, bar the blistering Put it there, Pal.

..had a double 7" single of "Heads down no nonsense mindless boogie", I seem to recall.
Track 2 was a forgettable little number entitled "Thank You", whilst for track 3 the band served up the identical song, but replaced the word "Thank" with a much ruder verb beginning with F.
Why can I never remember important things, but always recall rubbish like this?

had a track on their 'Strange Times' album called 'Tears' that came in 2 flavours. The original album release had an acoustic version of the track while the 12" version had a full band version.

Here are the two versions:

Two versions of 'George Jackson' on the A & B sides of a single, Most of the alternate BOTT is also now officially out there somewhere. And four studio versions of 'Mississippi'. Does that count?

Roxy Music - the single version of 'Angel Eyes' bears little or no relation to the LP version. And Byroni re-recorded some tracks from the fist Roxy LP on (I think) 'Another Time, Another Place'.

Not a name that gets bandied about here very much, recorded Turn To Stone on Barnstorm and So What which came out within about two years of each other. Judging by the couple of fillers that were on So What I assume he was well short of material.

Later covered by Dick Emery in his seminal sophomore outing
"Hello, Honky Tonk!"

Re-recorded (from the eponymous) "Life is Sweet" for "High Dive"

Slightly off topic but can't let Retro's dig at this album go unchallenged.While it can only ever be a matter of opinion,I must say the record in question comprises some of my very favourite RT songs."Woods of Darney",Cold Kisses",Burns Supper",and "Dark Hand Over My Heart" are all up there.Also,another Joe Walsh here."At the Station" from "But Seriously Folks" owes quite a bit to "Falling" from Joe Vitale's "Roller Coaster Weekend".

No Cars Go appears on their debut self-released EP and in a version on Neon Bible that nicely illustrates the huge leap they'd made in the interim.

...the egregious practice, common in the 80s, where a band would do a "new version" or wholesale "remix", invariably hideous, of an old hit to bait a greatest-hits album or suchlike with the illusion of newness. Psychedelic Furs did it with Pretty in Pink, the Police did it with Don't Stand So Close To Me, Bowie did it with Fame (Fame '90 is truly one of the abominations in the DB catalogue), and how many bloody times did New Order give in to the temptation to tinker with Blue Monday, each time only serving to render the perfection of the original all the more obvious?