Pretty Permalinks requires outofthebox the module mod_rewrite. This module is a workaround to use pretty permalinks without any rewrite rule. The errorhandling – customized errorpage – will be used to resolve pretty permalinks. mg404Rewrite-Modul sends HTTP-Header-Code depending on the request.
If you have any posts to permalinks, you can try to activate PostProxy to resolve this issue (configurations / misc).