Well, I also have this extreme screen flickering when playing Deus Vult; no posting related to this topic could give any help so far (rename avi folder, quit programs, services, 16bit depth etc.).
This is my first Paradox game where the issue occurs; since AoD also had it in the first versions I wonder what they changed in the patches.
Maybe its my ATI card...
Currently I can't play the game, too bad.