I fixed it!! Woohoo!!! After much research I found similar issues with IIS 6 and the handling of redirects. I was lead to this page: http://ikailo.com/94/url-modrewrite-workaround-iis-60/ which has a fix for IIS6.. Well, with some tweaking and some magic I was able to come up with a fix for IIS7. it is as folows:
2. You have to now configure your IIS7 installation (in my case IIS 7.5) to allow for custom redirects and to use this page for 404 errors. To do this you have to do the following:
a) Open up IIS configuration manager (separate install for iis 7, included with iis 7.5).
b) Browse to system.webServer/httpErrors
c) unlock defaultPath
d) unlock allowAbsolutePathsWhenDelegated
e) set allowAbsolutePathsWhenDelegated to TRUE
f) go to Error Pages
g) right click on 404 and click edit
h) select “Execute a url on this site” and set to /404-handler.php, hit ok
i) right click 404 and select Edit Feature Settings
j) set to custom error pages and path to /404-handler.php and path type to execute url
I then had to reset IIS and IT WORKS!!! Woohoo!! I hope this helps others!!
Hey Paul, I am getting the same exact issue. Did you ever find a solution? I tried resetting the permalink structure as Nick recommended but it did not work for me.