I am using Internet Explorer 8, and had similar issues. I could upload from the server the upload page is hosted on, in IIS7. I could also upload from another different server but on the same domain as the webserver (that hosted the upload page). Both these worked.
But the upload from a PC that was not on the domain, did not upload, and gave the 500 error. I finally added the upload site on internet explorer to the Trusted Sites, and it worked fine. :)
Before that I checked rights on folders etc, and that was all ok. Also had size issues, then got a blog that said I should add:
<requestLimits maxAllowedContentLength="2000000000" /> <!-- bytes -->
</requestFiltering>
to the applicationHost.config file on the webserver in location C:\windows\system32\inetsrv\config\
In addition in IIS7 I also had to check the asp properties in server manager for the website that the upload page is on, changed the Limit Properties \ Maximum Requesting Entity Body Limit to match the size in the applicationHost.config
file.
This is a classic asp website.