You say that network services are configured correctly but I think you should check again. This sounds like a classic network config issue.
Here are a few things to try.
1) From a DOS prompt attempt to ping the mail server by name. I expect it will fail.
2) Try to ping the mail server by IP address. If it succeeds, there are likely name resolution issues on the network or perhaps just with this PC.
3) Try configuring the mail client (resolving the user name) using the mail server'sIP address, rather rather the server name. If it works, again, there is likely a name resolution problem. If not, ...???
4) If available, try pinging the workstation from the mail server to test for network connectivity to the client.
5) As atemporary test, create a hosts or lmhosts file containing the name and IP address of your mail server on the client.
Lastly, make sure that you have a valid WINS address in your network configuration. Ping it to make sure it responds.
Make sure you have a valid DNS entry on your network config. Ping it to make sure it replies.
If you are using DHCP, remember that any entry in the net config settings will override the DHCP settings. If an entry is in there by mistake it can cause problems.
Use winipcfg or ipconfig/all as appropriate for your O/S to see what the system is really using rather than relying on the network control panel.