That was like me, I gave up on trying to fix it, low and behold my computer illiterate brother found a solution.
Did you try this?
Go to 'Battlefield 3' folder in origin games and delete the 'pb' folder and the 'pbsvc' file I think its called (has blue PB icon)
Download 'PBsetup.exe' from evenbalance and extract it to your 'battlefield 3' folder.
Run PBsetup as admin, 'add game' 'Battlefield 3'. 'Check for updates', allow to update.
go to :origin games / Battlefield 3 / _Installer / punkbuster / redist and run 'pbsvc' and 'install/reinstall punkbuster service'.
Game should then work
Worked for me, every time I restart I have to redo that process without downloading the setup, just delete pb folder, add game and update in pbsetup, then install/reinstall from the pbsvc.