I know there are a lot of posts and many people can't get Hamachi working so I'm posting a quick guide on how to 'Direct Connect' which seems to be the most reliable method...
We will be creating a direct connect shortcut on your desktop as it avoids any issues not being able to see hosted games etc.
How to 'Direct Connect':
Navigate to the following:
1. Find the file 'Borderlands.exe' and create a shortcut to it on your desktop. (just right click and drag to desktop choosing 'create shortcut here') - DO NOT move/copy the file itself.
2. Get Hamachi (unmanaged will be fine)once installed create a network, once done get your friends to join it. You should note that you need to right click your name and 'Go Online' if you do not have a green dot (its grey etc) - Download is here:https://secure.logmein.com/products/hamachi/download.aspx
3. Decide who will be host, who has the best broadband/PC?
4. In Hamachi right click that person and choose copy IPv4 address, paste it in notepad and it will look something like this: 18.104.22.168 (this is not a real one...)
5. For everyone that is not host have them right click the shortcut on the desktop and in the box labelled 'Target' you should see the path to your installed borderlands folder (where you copied the shortcut from) it might be a different drive letter but example below:
6. Copy the host Hamachi IPv4 address from your notepad and add to the end like this:
7. Click apply then just hit OK and close the properties window
8. Have the host launch the game and create a public LAN game
9. All the party (apart from the host) can now launch the shortcut you just created and after pressing Enter (past the intro crap) you should drop right in to the lobby, happy days
Thats it, once its done you just follow step 8-9 in future until this crap is resolved. You might have a few issues if the Gamespy login prompt keeps popping up, to get round this open the game and on the prompt untick the auto login box and then hit login. It will fail but the auto login preference will be removed, then you are free to exit the game and follow steps 8-9.
If you decide the host was a bad call then just exit the game and change the Hamachi IPv4 to the new and follow the same process (host creates game first, then launch the shortcut).
Hope it helps.