Thanks for the link, Kelly. Unfortunately, everything that the article suggests has already been implemented. Just to clarify, we're hosting the application on Server 2008 and will be accessed with Windows 7 machines.
There is something else that could cause the issue. The Website itself is not under C:\inetpub\wwwroot. It's located on another drive on the server and set as another website in IIS. So, in IIS7.5, under the "Sites" folder, there's "Default Web Site" and "MyWebSite". It's the "MyWebSite" that's being accessed, but the ArcGIS folder is located in the "Default Web Site". This doesn't seem to bother the Map Services for anything else, but I wonder if the proxy is having trouble with this. I am setting the proxyUrl in the Javascript to the absolute path though so I didn't think it'd have that much trouble.