The problem has been fixed now after an EAgent escalated it to the next support tier. I will repost here the instructions I was given in case anybody else runs into this issue.
- Uninstall Origin
- Delete the game folder in c:\program files (x86\origin games
- Find the licence folder in c:\programdata\electronic arts\ea services and delete it
- Delete the origin folders in c:\programdata c:\users\username\appdata\local and c:\users\username\appdata\roaming
- Use CCleaner to clean the registry and clear both cache and temp files
- Run DOS as admin and execute the commands "dism.exe /online /cleanup-image /restorehealth" and "sfc scannow" then close the DOS box
- Install Origin
- Redownload BF4 and install it
