Pretty Permalink Issue

Hi, I have a problem with my permalinks not working in any other format than the ‘standard’ option. I just get a 404 error. Having researched for a very long time, I have tried adding a blank .htaccess file (with 666 & 777 permissions at different times) which seems to be the most common issue. I have also tried the ‘mod_edit’ approach and another .htaccess script but linkies still no worky.

As soon as I switch back to the standard setting, all is well again.

I really need the permalinks in ‘pretty’ format so has anyone got any ideas? The only other theory I have is that the server may be blocking it somehow but I have no information on the server software (it’s hosteurope.de if that’s any help?).

Any advice greatly welcomed!