To all those still searching for an answer here, this is what Paul told me to do - and all of a sudden, date recognition worked flawlessly:
In System Preferences I had only German installed. Since some of the date formats where not in a format usual for the German language, but rather English, I had to install English as another system language. This was done in about 1.5 seconds (and yes, you still keep your primary language on your system).
Once English was installed on the system and available in system preferences, Hazel recognized other date formats, too.
Perhaps this piece of information can help one or the other here. Post it, if you are successful with this.