This is a list of albums that are important enough to get. I will also mail you some pictures of the album sleeves because some albums came out with a second (or even a third) alternate sleeve. I hope this list will help.
To answer some of your qustions; "Separate Ways" was released on CD but in another country. The album came out in two versions. A British release (Pickwick CDS1118) with a highway on the background and a USA release (Camden CAS-2611) with a country road on the background. The last one is the original.
The album "C'mon Everybody" was also released in two versions. The original version has a 1970 picture on the sleeve while the re-release has a wedding picture on the front cover. I'm not sure if the tracklist is exactly the same. But I will figure this out.
There was also a re-release of "His Hand In Mine" in 1976 with the same picture of Elvis but with clouds in a dark blue sky on the background.
And as you already mentioned a re-release of "Frankie & Johnny" which contains the same songs as the original but with a different cover.
Elvis Sings Flaming Star (1969)
This is a compilation of songs that didn't made it to the soundtracks.
From Elvis In Memphis (1969)
Studio album and an important one. This one marked Elvis return. The songs were recorded in January/February 1969
Elvis- From Memphis To Vegas / From Vegas To Memphis (1969)
A double album. Album 1 is Elvis In Person (live in 1969). Album 2 is a studio album called Back In Memphis (studio album recorded in January/February 1969) Both albums also came out separately in 1970.
Let's Be Friends (1970)
A compilation of "left overs" but a good one.
On Stage (1970)
A live album compiled from material from 1969 and 1970.
Worldwide 50 Gold Award Hits, Vol 1 (1970) 4 Albums.
The first box with songs from 1956 to 1970.
Almost In Love (1970)
Another compilation with "left overs" from the movies "Live A Little, Love A Little", "Charro!" and "Change Of Habit".
Elvis' Christmas Album (1970)
A compilation of older songs with two new recorded songs. This album was re-released several times with slightly different sleeves. The original one has a full picture from the movie "Speedway" on the cover. This one is hard to get.
Elvis - That's The Way It Is (1970)
A combination of live songs (from the documentary) and studio takes. A superb album. This is an album I would take to a deserted island.
I 'm 10.000 Years Old - Elvis Country (1971)
A country album. Also a must have. All studio cuts from 1970 & 1971.
You'll Never Walk Alone (1971)
A gospel compilation of songs recorded between 1957 and 1969.
Love Letters (1970)
Studio cuts. Good album. Songs recorded in 1970 & 1971
C'mon Everybody (1971)
Compilation with some movie songs that first came out op ep.
Elvis - The Other Sides (1971) 4 Albums.
A compilation box set with the b-sides.
I Got Lucky (1971)
Compilation. Could have been called "C 'mon Everybody Vol 2".
Elvis Sings The Wonderful World Of Christmas (1971)
A studio Christmas album and a **** good one. All songs recorded in 1971. Also released with two different sleeves. The original one is with Christmas presents on the front.
With this I would like to conclude my list up until 1971. When I will get back from work this afternoon I will continue with the list from 1972 until 1977.