Is it possible for two users to remotely log in to a Mac simultaneously?
Yes - Lion makes the distinction between sharing the current screen and letting a different user log in. This brings multiple login to Mac OS X in an official way.

When you connect from another Lion mac - this window shows how you can select either access method.



A few VNC client apps (Like Screens for iOS and Screens for Mac supported this when Lion was released. Several popular VNC clients didn't work initially due to this change (and may need updates to work with Lion's new screen sharing method).