I had a suspect though: Compiz. Changing the Desktop Effects to none - effectively shutting down Compiz - turned full screen video playback back to normal; no more hick ups, framedrops or anything. But toggling Compiz on and off isn't a solution. It's a workaround and thus feels wrong. So, I had to dig through the Internet to find a solution.
Many, many forums, blogs, bug-sites and other websites have been written full on this problem. Especially the combination Compiz - ATI fglrx cards seem to experience the video playback problems. I found many "solutions", ranging from adapting Xorg.conf with custom settings to fiddling with the aticonfig tool. However, judging from the comments on these "solutions", they seemed to work for only small parts of the populus and certainly not for the majority.
As I didn't want to mess up my system with complicated sets of script alterations of which I wouldn't be able to keep track of after a couple of rounds trying, I decided that I'd either have to go with the Compiz-shutdown-workaround or have to come up with something else. Shutting down Compiz isn't too complicated if you use the Compiz Fusion Icon in the system tray but it also changes your desktop appearance. Especially if you use things like the Avant Windows Manager like I do as this relies on a composited desktop.
But first I thought to go through the CompizConfig settings. This is easily found through System->Prefferences. Looking at each option, I tried to predict what it would do. I must admit that many aren't too obvious and the tooltips aren't very explicit either.
Under the "Tools" header I found "Video Playback". Now, I haven't got the foggiest on what that does or is expected to do, but I figured it might conflict with proper video playback in other software. So I toggled that off and retried full screen video playback. And... tataaa... it worked fine; as if Compiz wasn't running!
I haven't seen this solution anywhere else, so I am wondering if others experience toggling this setting to off solves their problems. If it does (or doesn't), please leave a comment for others. Thx!
Important update: You will have to close windows that are frequently updated or switch to a clear desktop in order to avoid the underlying windows to flash black boxes through your video. E.g. I have to close all active screenlets when I watch video, as these are updated every few seconds and flash through the full screen video.