Permalinks in IIS 6

I’m setting up wordpress on a client’s site an I’ve run into a problem with Permalinks and their server running IIS 6. I’d like to be able to have permalinks set up a custom structure with /%postname%.
I haven’t been able to get it to work without including index.php. I don’t have access to the set up of their server, but I found this link (http://www.deanlee.cn/wordpress/url-rewriting-for-wordpress-under-iis/) and had their server admin follow the steps to allow for pretty permalinks. I’ve found other articles describing the same process but I haven’t yet found a solution for this problem. Whenever I try to visit a page on the site (example: http://www.thesite.com/contact), I get a 404 error.
Any other suggestions or ways you’ve solved this issue?