Google search asks me to enter a captcha, at some point it refused to let me search altogether

Google claimed there was suspicious search activity from my computer when it stopped letting me search altogether. Before that I had to enter a captcha more and more often in order for Google to answer my search request. I search only infrequently.

I scanned my PC - started the scan from a special anti-virus USB boot system so that the actual Windows 7 of the PC was not running, so no root kits or anything could influence the result. I ran two different anti-virus apps. None of them reported anything.

Since my router had not been supported since 2011 I thought maybe that device might have been hacked. So I got a new well-supported one.

All was clear, Google let me search again - but now, less than a month later, I just had to answer a captcha again before Google would let me search.

Does anybody have an idea what might be going on here? Unfortunately Google does not provide any specifics in their messages, neither do their help pages about this subject.

I also ran the Google Cleanup Tool and it reported nothing.

EDIT:

So I looked at my traffic with Wireshark. Unfortunately that's next to useless. I only care about traffic to 1e100.com - Google search servers. Well, there's plenty of such traffic - if Chrome is running. Even with the only open tab being an empty one, i.e. no page is loaded. Someone is chatting with Google servers, but it may very well be normal for Chrome, even though I wonder why it needs to chat with Google servers so much when there is nothing going on in the browser. Traffic analysis beyond the fact that communication takes places is not possible - it's all SSL. So I'm not the wiser.

EDIT^2: (25 September, 2015) I ended up buying a new router. Maybe my router got hacked - there have been no updates for the firmware for five years. For the months since replacing the router I have not seen the above issue.

UPDATE^3: Even with the new router I had this issue again - but only briefly (once). This helped me discover that I had just enabled a Chrome extension just before Google warned me. I disabled that particular extension again and Google never warned again. At the time I posted this question here I had the extension running too. The extension is BetterTTV - I add the name reluctantly as I don't have any proof and didn't examine this further, so others may want to look into this a bit more before raising your pitchforks against the extension. Noteworthy: The extension seems to load much or most of its code from the Internet. The author wrote this was to work around Google extension website adding new versions with too much of a delay.

Update^4: A few months later (Dec 2015) with the new router and without the mentioned Chrome extension, and I have not had the issue any more except for what I wrote in update #3.

As suggested by Enis P. Aginić, Check for outdated add-ons in google chrome.
If you tunnel you web traffic through a web-proxy disable it temporarily.
If you use VPN, disable that too.
I had the same problem, solved it by disabling "Zenmate" in chrome( Add-on for web proxies).

Web proxies usually talk with servers in the background, that might be the reason google is paranoid about and it might be the reason it's asking to fill out CAPTCHA

Assuming there are no other devices on the network (smartphones, game consoles, anything) your PC is most likely the source of the problem. According to Google you have "illegal search" traffic. My guess is you have some sort of outdated/broken app or add-on causing this by sending malformed search requests. It's not necessarily malware, just some crappy peace of software. Google will detect it as a bot and try and confuse it by throwing human verification at it.

Now fooling Google by resetting your router (or changing it) may be very difficult, but you can try rebooting your router (you probably get a new IP) and use incognito mode to see if it asks for captcha again.

My advice is to disable any add-on you don't need, sweep trough your add/remove programs, run chkdsk on your system drive as you may have a corrupted installation somewhere.

For example I had a user sending requests to g.ceipmsn.com with some parameters every few seconds. After some traffic analysis it turns out their Bing Bar was broken.

You could also try firewalling all outgoing connections and let apps out one by one, there is a good article about blocking outgoing connections here. It may help identify your offending software.

If all else fails, good old wipe-and-reload may do the trick.