When I clicked on that link it sent me to Goodle and 'JohnDoe@yahoo.com' was in the search bar. Exactly what I had typed to find the site in the first place.
That would be your browser's autocomplete, or something similar, most likely. Also, if you truly mean the "Search bar" then it's contents won't change when you navigate sites. It would still have your original search term as you followed the various links.
Although I find it odd that they would list google as a reason to reject your registration, since most registrations are automated and therefore it wouldn't be particularly feasible to create a software implementation that is able to analyze google results for completely unrelated queries about other peoples E-mail accounts and somehow base a rejection on that.
Bottom line- it's not possible for anybody (except maybe google, and of course your own browser) to ever know anything you searched for. Google just knows your IP searched for a certain query. I doubt they keep a particularly detailed record of that type of thing though, due to a number of privacy laws in various countries.
The thing is, even if it were possible, the first thing to have to happen would be that said person would need to wonder if people are googling them. In this case, you googled (to my understanding) the E-mail address (in a misguided attempt to see if Person A from IMDB (which to my understanding doesn't even have a forum, and if it did would be unlikely to publically reveal the E-mail addresses of members (or was this person actually directly E-mailing you?). So, the person would not have to wonder wether somebody is googling their name or address, but rather wether people are googling for their possibly disposable E-mail address. There is no reason for them to wonder this, and even if they could find this information, it wouldn't be particularly useful. What if they were able to know you googled them? I fail to see what particular significance it might have. (Again, most of that was hypothetical, there are far too many "barriers" to getting this information and that information would be particularly useless in almost any context).
When you click on a link which is a Google search result, the site that you go to via the link gets no information whatsoever about the Google search that you had typed.
Not true. If the browser fills out the REFERER header field then the site that is visited via the google search get's the entire URL of the search page; the URL can be parsed to reconstruct the exact search that was made. But that only applies to websites; it's doubtful that a website would keep that information around throughout the entire registration process, and even less likely that they would reject a registration based on that information.