I moved everything from 1und1.de to strato.de because the old web host was too expensive and had crappy service, now the new web host is less expensive and still has crappy service and on top of all that mod_rewrite is not working and producing internal server errors. Turns out there are a lot of unhappy strato.de users facing the same problem.
All my links you find via search engines have permalink structure and are now broken since strato.de just doesn’t offer mod_rewrite with any of their web hosting packages, at least that is what I am led to believe. This is easily the death of any blog if suddenly none of the 1000s of links search engines have cataloged stop working altogether.
How such a simple feature can not be part of a “PowerWeb Advanced” package, esp. when Strato.de advertizes their webspace to be WordPress friendly is beyond me. If you have made similar experience, feel free to comment.
For now I am using this plugin which (ab)uses the 404 error document as a workaround to use permalinks without mod_rewrite.