IIS FastCGI does support URL's that use path info (e.g. /index.php/foo/bar). When I tried it sometime ago I was able to use customized permalink structure. However, I used PHP 5.2.5 and Wordpress 2.2; may be latest version of PHP or Wordpress has some changes that break that?
Do you get any errors when you try to use custom permalink structure?