The only service I have that problem with is Microsoft since it's a merge of like three different accounts (MSN messenger, Skype, and Office365) so I can never remember which is the right one.

Otherwise my rule is to use the central part of the ___domain name (no www or TLD), or it's easy enough to just search my email archive for messages from whatever service.