With both you’re hoping there are no logs. It’s odd you used a different scenario where search intentionally makes the call to save searches linked to you and sell to ad companies, instead of sticking with the same scenario used for the vpn. You don’t want the search engine to log your searches linked to your ip or a user id that ties back to your billing info.
Then there’s a non-zero chance that either the VPN or the search or both are actually honeypots which not only log everything, but have a whole monitoring and alerting machine setup.
You’re more trusting than I. I assume the VPNs are no where near anonymous. I assume paid search is no more private than any other search. I assume the government doesn’t get or need warrants to know what we do online (do you think Prism just went away or hasn’t been replaced with a superior iteration?)
If anything paid search is more privacy invading than free ones. With free ones when logged out they know your IP which could serve any number of people so it wouldn’t be shocking that the searches being look into came from someone else on your connection and not you (tor relies on this), whereas with paid search you must be signed in to use, with an email address tied to you and a cc tied to you, all plausible deniability goes out the window.