My gf googled a Mexican restaurant neither of us had been too on her phone and when we got in my truck literally 5 minutes later android auto maps on my phone suggested it as a destination. If they can do this, they can get your other email addresses.
Wait, why? If both of you have your location info turned on then this seems like a trivial correlation to make, especially since both of these are Google's own services.