I agree, it isnt easy but it is possible. I am assuming that you have control of the configuration of both Moodle instances, so you can set their authentication method to whatever you want?
In that case, you could try using an external authentication system and getting both Moodle's to redirect to that for login. There are a number of auth plug-ins already in Moodle which might be suitable, or you can write your own to talk to whatever other system you have.
Or you could write your own authentication plug-in that will log you on to the second Moodle automatically if you're logged on to the first. I've done that before, and the tricky part is in handling the fact that users might have different ID numbers on the two servers - in the end we went for an external auth because it was easier to manage.