Unbelievable. After 4~ hours on the phone we found the problem.
The geeks at GoDaddy messed up big time likely at the time when they migrated their servers to Apache 2.4 in the last month.
On their grid hosting plan you now have to specify the folder your website is located in, when you make a relative path. Unbelievable. One day you wake up and everything that all the websites that were working for 5 years are broken. No notification, no warning. Thousands of dollars down the drain.
Redirect /path.html http://example.com/correctpath.html
has to be written like this:
Redirect /foldername/path.html http://example.com/correctpath.html
<sigh>Now that I changed all my redirects, I'll have to constantly test that they don't change it all back the way it was.</sigh>