How do I find my Apple ID connected to my iphone if the phone has been lost? I've lost my phone and in order to access iCloud I need my Apple ID however I don't remember the one that is linked to my iPhone.  What can I do to find this out?
There doesn't seem to be any easy way to do this.

To do it by trial and error, you can go to the iCloud web-site and login with each of your Apple IDs and try the "Find my iPhone" feature to locate it and/or send a message/tone to it.

If you have any other iOS devices with a similar setup, you can check on them as well.