Cisco AnyConnect Secure Mobility Client 3.1.03103. The VPN Agent service is not responding

It somehow started working again. For the sake of helping other people in my same position I will add the step I took that might have solved it:

A few months ago I installed Spybot Search & Destroy and used the immunization tool that came with it. From my searches on this topic I noted some people mentioning that the Cisco client needed to adapt a host file to work. Apparently Spybot decided that the client was not allowed to do this. After undoing the immunization and uninstalling Spybot the vpnagent service magically started working!

I'm not 100% sure this was the actual solution since my VPN worked before even when the immunization was still on. However I suspect that the conflict between Spybot and Avira antivirus might have something to do with this non-deterministic behavior.