It’s taken me months to get this sorted, but I finally found a way to get nice, pretty permalinks for my wordpress installation in Microsoft’s web server IIS. Permalinks are natively supported by the Apache web server with a little help from the Mod_Rewrite module. Unfortunately there isn’t any equivalent module built into windows.
I downloaded the WordPress URL rewrite plugin and it worked without any installation hassles whatsoever. Be warned though – you will need root access to your web server as the .dll needs to added to the ISAPI filters on IIS.
Hopefully the plugin works for WordPress Mu – going to try that next.