Because cookies are bound to a domain. So once Gmail moved to google.com/mail, the Gmail cookies started carrying over to the search on google.com, meaning that Google could correlate your search terms with your account.