It most likely is related to the format you're recording your video as.
You say you're recording from a video game. Even if you're recording an AVI, it's not likely a DV-AVI, and that strange codec is responding funny in Premiere Elements.
The easiest way to see what codec your video is using is to open it in Windows Media Player and select File/Properties.
Hmm, I am indeed using Fraps, but I don't see anything in that thread that helps. Also, that article seems to be asking for the user to adjust each individual clip, but I've got way too many clips to be adjusting each one. I need a fix that eliminates the problem altogether.
It is a strange problem because it comes and goes and is only a problem for certain specific clips when it does happen, yet the problem does not appear to actually be from the individual clips, since they seem in-sync while viewing in media player, though it is possible I simply can't tell they're in fact out of sync.
This also seems to happen even in movie maker, if that means anything.
Unfortunately, the video capture programs do not consider later editing. That is the drawback. Other than making corrections for those OOS Clips, there is not much hope. Even the Adobe video-capture program, Captiva, leaves too much to be desired. They just do not think of editing.
Good luck, and sorry that I could not help,