The SOCKS 4.0a choice in MSN Messenger is actually broken. I've reported the problem to Microsoft, who said (after a month or two) that it had been sent to engineering. Even with the amount of time between my reporting it and the release of MSN Messenger 4.0, it still appears to be broken (although I haven't verified it's the same problem).
In short the problem is that if MSN Messenger attempts to negotiate a SOCKS 5 connection, not a SOCKS 4 connection. This isn't a problem for most SOCKS servers as they support both SOCKS 4 and SOCKS 5, but a SOCKS 4 only server will simply not connect.
If you want to use a SOCKS 4 server for MSN Messenger, I'd recommend you try either Proteus (
http://www.proteusx.com/) or Adium (
http://www.adiumx.com/) as both support both SOCKS 4 and SOCKS 5 to connect to MSN.
- proton