Permalinks in WP 3.0.4 Station theme (free)

I’m having problems getting my permalinks to just /%pagename%/, I can’t get rid of the index.php. Whatever I try I get a 404.
I see it was a problem in 2.6 that got fixed in 2.6.1 so I wonder if that bug re-occured? (I couldn’t find this mentioned though, but maybe it occures only on new websites?)

What I did try already:
My website is on a Microsoft IIS 7.0 server but it is rewrite enabled. So I created a new .htaccess and put in just the code as per codex into it and uploaded it to my root directory.
It doesn’t seem to be a rights problem as WP always confirms that the permalinks got updated and that’s what I see as well when I go on edit/page.
From what I can see it has nothing to do with the theme I’m using – the free version of Station.

Anyone has the idea how to fix it – running out of ideas here.
Thanks.