"Hmmm, suppose google did become a commonly used verb that meant "to search online." "

I'd say that has already happened.

"And suppose that a website relabeled all their search buttons to read "google" even though the underlying search had nothing to do with Google (tm) the company."

That would be wrong of them, as any Reasonable Person clicking a button marked "Google", during the act of submitting a query to a search engine, would expect that search engine to be Google (tm).

"What recourse would Google (tm) have? I might buy Cory's post as it applies to nouns, but I'm missing something as it applies to verbs."

THEN their recourse is to send out those lawyer letters, followed by litigation if the offending search engine does not redress.