I deleted and paused my Google Web History some time back, thinking that meant Google would stop collecting "my" web history. This morning I was changing some Google account settings and clicked on Web History. They had started maintaining web history for me again. So I again had to delete everything and "pause" my web history. Apparently pause does mean pause, and Google pops the account off pause willy-nilly, or by some algorithm known to them, but not to their users.
The thing to do is to remove the web history. From Google Account Help:
Using Web History: Deleting
You can delete Web History from your Google Account at any time. Just follow these steps:
Click the My Account link from the Google homepage.
Click Edit next to 'My products.'
Click Delete Web History. Make sure you're signed in to your Google Account to see the My Account link.
Note: Deleting Web History from your Google Account will erase all items from your Web History and stop your Web History from being recorded in the future. You can also remove individual items without deleting all of your Web History.