Yes the Punkbuster was a one time error so far.
Yes, that video captures the delays. The freezes also occur since the beginning but they don't happen as often. In fact, the delay is always present while the freezes may happen sometimes during the game (it's rare for it not to happen at least once per game). When I started this thread I forgot to mention the freezes, but I reported them somewhere in this thread earlier.
Yes, some delay is to be expected, but the thing that seems off is that comparing with previous FPS games that I played in the last 10 years (CS Source, BF 2142, Halo Combat Evolved, Urban Terror, BF Heroes, FEAR, Team Fortress 2, L4D, L4D2, Borderlands 1 and 2, BFBC2...) this never happened. As I said previously, I jumped right from BF Bad Company 2 to BF3 (just had to wait for Origin to download BF3) and I noticed this awful delay. The even more surprising thing, to me, is that BFBC2 as less servers than BF3 (as it is expected) and with worse ping and the delay I noticed there was the "normal" delay everyone would expect (there is always some delay except in LAN parties).
Also I tend to play in different servers and different maps (to complete assignments).
No, I have thought about OCing, but never done it.
Thanks again for your support!
UPDATE: I was currently using the 13.4 Catalyst and thought that maybe rollback to 13.1 could solve my problem. However it did not solve my problem, the delays kept happening.