For the past six weeks that I've had my iPad, I've fought with my office network, because it uses a Microsoft/NTLM authenticated proxy server which wreaks havoc on the iPhone OS's ability to use the Internet effectively (especially for third party apps).
After reading through countless forum support requests for people asking the same questions, I've finally found a (mostly) workable solution for this problem—at least for most apps and browsing on the iPad.
Doubling the Proxy
Since the iPhone OS seems to have a pretty hard time dealing with proxy authentication (most apps don't act like there's even an internet connection, even if Safari will work through the proxy), I used a solution I often use on my Macs at work: doubling up the proxy.
Basically, you can use an application like Authoxy on the Mac to make the Mac translate all its web traffic through a special internal connection, which gets messaged correctly by Authoxy to work with your company's proxy server.