Trying to provide pretty permalinks on a IIS install of WordPress is something of a problem. The solution is a bit of a hack, but works.
1) Create a custom 404 page as per these instructions: http://dotnetcodebytes.blogspot.com/2011/11/remove-indexphp-from-wordpress-on.html
2) Specify the 404-error.php created in step 1 as your custom 404 page (you'll need access to an IIS admin console).
3) In WordPress, define your permalinks as: /index.php/%postname%/
