This is a frequent question for most IIS users on how to get permalinks to work in WordPress, it's fairly simple really once you know how of course. So the problems are, you're using IIS so using mod_rewrite won't work, you're on a shared server so installing a mod_rewrite alternative for IIS is not available either. You can have URLs with a index.php in them (for example http://www.yourdomain.com/index.php/2009/03/17/getting-permalinks-working-in-wordpress-on-iis) but they're pretty ugly looking and doesn't fit into the URL standards (in other words, it's just nasty).

WordPress Codex has a very useful page about working with permalinks, there's one solution that uses 404 error pages, however when you look at what it does it's very slow and again very nasty. The 404 error solution makes the server try to find the page, it doesn't exist so the server directs the user to the 404 error page, the 404 error page then does it's own working out to figure out where the user should be going, and then it would make it's own HTTP to the correct URL.

This example would work great if only it didn't make a HTTP, so what can we do with this example to make it more efficient.

<?php
   $qs = $_SERVER['QUERY_STRING'];
   $pos = strrpos($qs, '://');
   $pos = strpos($qs, '/', $pos + 4);
   $_SERVER['REQUEST_URI'] = substr($qs, $pos);
   $_SERVER['PATH_INFO'] = $_SERVER['REQUEST_URI'];
   include('index.php');
?>

* Put the above 404 error script in the base of your WordPress directory.

* Set your site's 404 Error Page to the file above

* Setup your permalinks in WordPress -> Options -> Permalinks

Because it's including the index.php file into the script, it's utilising the functionality that is already present in WordPress.

Resources
* Pretty WordPress Permalinks on IIS
* WordPress Codex Permalinks
* 404 Error Solution