Are you using WINS on your network? Does you laptop get an IP address by DHCP? If the answer is yes to both questions, you might want to do an "ipconfig /all" and make sure all the WINS and DNS settings are correct.
Also, check that the NIC in the laptop is connecting correctly to the network - from time to time I see computers that autonegotiate poorly with the network switch and you end up with a half-duplex connection that works okay for browsing but drops RPC calls of the type that Outlook uses to communicate with Exchange.
But you could also create an LMHOSTS file and see if that helps. In a default install of Win98, you'll find a sample file called LMHOSTS.SAM in the c:\windows directory. Just edit it with Notepad and save it as LMHOSTS (i.e. without the extension) and see what happens.
paul