There are two ways (that I know of) to do this.
First, use a 3rd party URL rewriter. Sorry, but this is really the best way. There are a couple of free ones if I remember correctly, but to get anything resembling the functionality of Apache's mod_rewrite you'll need to cough up a few bucks.
Method number 2 involves a bit of recoding in WordPress. I've used this technique several times now with 100% success. IIS can use any file (including ASP or PHP files) as a custom 404 (file not found error, which is what you'll see if you try to type a "pretty" WordPress URL on an IIS server) page. If a new file can be created to act as the 404 page and pass control to the necessary existing pages as needed, this can work. In ASP, the call is Server.Execute("filename.asp"), but I don't know the equivalent PHP.
Not a job for a beginner to work on. I highly recommend the first solution.
The third way is simply to get Apache installed on the server. Worked for me :)