Try with VBR 2-pass and tick Use Maximum Render Quality to on. See if that improves the quality.
Looks the same.
The main problem is that you are scaling up the video. Is it possible to make the game screen larger so that you capture at a larger size than 960X720. That is pretty small nowadays. Does the game get bigger?
If not, you may want to export the video at the size it is and not worry about people playing it back full screen.
Otherwise you are trying to create pixels where none existed before. You viewers might get better results with their monitors scaling up the video than with you doing it.
Weird thing is, I recorded this video at 1280x720, and the raw footage looks flawless. Heres a screenshot to show the raw file in explorer, showing 1280x720. http://gyazo.com/58c6858cc33a272b21b3e1ac2b082d5c
Did you create the sequence by dropping your video on to the New Item button?
What does Premiere Pro say about the frame size in the Project Panel?
If it says something other than 1280X720 perhaps you need to record with a different program.
Edit: By the way, you can insert images on this forum. Click on the little picture of the camera.
I just changed my sequence settings and exported a video. It asked me if I wanted to keep the sequence settings or the video settings, I chose video. It looks better alright. This may have been the problem.