After Alexanders feedback, I fixed a bug in the WP plugin “Permalinks Moved Permanently”.
Before, the plugin would not work if your old permalink structure did not contain anything between the domain and the post slug. So this would not work:
The latest release (version 1.2) does.
If you have been experiencing this problem too, download the new version here.
Thanks again, Alexander.