I've had no trouble opening two instances of VLC on WinXP and playing different videos full screen on different monitors. I'd like to try it on a MacBook Pro, but what are you using for dual monitors? Built-in and external?
Are you using a script to launch the player, to ensure sync?