"Should I reencode the video with more key frames, maybe?"
-> Yes, and usually "Photo Jpg", "Animation Jpeg" codec and those who have less time-encoded frames are more efficients. But I don't know much about codecs so maybe someone can give better advices here.
But It also depends on the plateform you are running it and the loader you use with pix_film: you can change it using "loader foo" message.
For example, on OSX I have:
[pix_film]: loader quicktime4linux
[pix_film]: loader AVF
[pix_film]: loader image
There is a VLC plugin somewhere that could help but I don't know where.
Also this might help:
Generally when I want to have a long HD movie with a good framerate to play within pd, I use ofelia library wich is far more stable and robust than Gem now.