Yeah, your VPN was probably allotting you an IP that has been used in DDoS attacks and is on blacklists for that reason. Free/cheap VPNs often have this issue (among several others).
The search function on sites is a common attack vector (because searches are usually unique, so the search has to hit the database and results/pages can't be cached), they'll hammer the search function from numerous IPs and cause the server to overload and cease to function or cause buffer overflows that would allow the attacker to compromise the system. The CleanTalk plugin obviously checks user IPs against those blacklists .