I don't know how often people actually Google themselves, I do sometimes but that is only to see if my 'personal SEO' efforts are paying off. Thinking back, how many times have you Googled your self? Paying for adwords on exec names are a novel strategy, just like the cake baking and song writing. It may work, it may get you noticed but it may also totally fail.
Well I googled myself just now, as a direct result of reading this thread. The last time must be well over a year ago. I don't think I even bothered the last time I looked for a new job.
Other way around :-) When you are looking you a job at a particular company, put up google ads for all relevant executives and hiring managers names, so when they google themselves, they find you. That came out zen.