I struggled the last few days with the exact same problem. Randomly the “Application failed to return a video frame” message popped up.. Did not matter which format I was exporting too (Adobe Media Encoder, FLV or WMVs) or XVID, DIVX etc.. they all bugged out at random points (although always at sequence changes) in the timeline.
Up until the moment I noticed the crop options on the Export Settings screen – I saw it wasn’t at default settings! I must have accidently touched it or something like that. It was set to crop 4 pixels from the left side. I changed this back not expecting it to fix any of my problems, BUT IT DID!
I spent quite a lot of time fiddling with options until that point. Setting Premiere Pro to memory optimization and changing codecs and whatnot did not help at ll. This seemingly unrelated crop option did however. 🙂