Here's a newspaper article from May 22nd, 1980:
http://news.google.com/newspapers?id=m98zAAAAIBAJ&sjid=SzIHAAAAIBAJ&pg=3761,2500650&dq=revenge-of-the-jedi&hl=en
The first trilogy concerns itself with the young Ben Kenobi and the early life of Luke Skywalker's father when Luke was a child, according to Lucas.
The next chapter is the end of the second trilogy entitled "Revenge of the Jedi" and is the conclusion of the conflict between Vader and Luke, he said.
and there's about 20 others with 'Revenge' mentions from just 1980.
*EDIT*
and yet here's another 1980's article with 'Return of the Jedi'
So, three years from now, he will not have to spend six weeks in Hollywood, in a sound-mixing room, to complete "The Return of the Jedi," the third "Star Wars" movie.