Utopian is onto something -- You could use Hamachi or something similar to create a VPN, and then just use windows file sharing to share folders. Then you can each install Subsonic locally. Problem is, the VPN and shared files will be very slow. I've heard people complain that Subsonic becomes almost unusable when large collections are shared from a linux NAS to a Windows server due to lag scanning, so I can't even imagine what the latency across-country would cause.
You could also get each of your collections on a NAS or some other device that will accept SSH. Rent a web server (small VPS should do it), and map each of your collections via SSH, then install Subsonic to share the combined library. Might be quicker. May not though, might just be universally slow for all of it.
Honestly, GJ51 was on to something with his first post. It isn't really realistic to network your collections and use Subsonic -- there isn't any way to make it work in a satisfying manner (ie - it'll take Subsonic, which is awesome, and make it a huge pain to use, if it works at all). Make it easy -- The two of you should buy a large external drive. Something like
this. One of you copies all your music to it and mails it to the other. He copies your music on to his drive, then copies the stuff you were missing back to the drive. Mail it back. Repeat every few months to keep your collections up to date.
You should also each install Subsonic locally and give each other accounts. Then you can still sample each other's new music in between trades of the hard drive, and use the download feature to trade small updates, like a new album.