You can search by email in most password managers.
Also if you use random strings that are not actually random (you just try to come up with something on the spot) you're very likely to reuse patterns for different third parties.
In the end it's more "stateless" to have a simple rule to attach an email to a given company, than maintaining a separate reference list (or lists! one in a password manager, the other in your email client).
But it's not very important, and mostly a question of personal preferences.