FRAPS puts out an AVI file that should work with Premiere Pro, I believe. It isn't too badly compressed because they don't have the time to compress it too tightly during the rcording of a game, or so they say. So it should look pretty good.
Windows Live Movie Maker can export to a file that is usable as a picture in picture in Premiere Pro.
Give it a try.