Although your nslookup results are wrong, this isn't necessarily a problem!
This is just what happens when you use a DNS server outside of your LAN.
If you do "nslookup www.taleworlds.com." (Note trailing period.) You should get the correct IP 72.55.156.59.
So, unless that fails, we actually are no further forward
The Devs asked for people to check with the Google DNS servers, so it would be nice to at least try that.
They are 8.8.8.8 and 8.8.4.4, I'm assuming as you are using OpenDNS you know how to change this.
Edit: The definitive way to find out what is happening (from an internet point of view) would be to:
1) Install http://www.wireshark.org/.
2) The Close any apps accessing the internet.
3) Start Warband in Windowed mode.
4) Start logging in Wireshark.
5) Attempt to "Join a Game"
6) Either dig through the results yourself, or .zip it and host it somewhere.