After generating the required locale on our development server and using setlocale to provide PHP with the locale to use the dates formatted with strftime would appear fully translated, as expected.
After reloading the page however, the dates were shown in the server's default locale: en_US. Reloading the pages multiple times resulted in almost a 50/50 chance of the dates being translated. Weird. What is happening here?
It appears that both Apache and Nginx webservers need to be restarted after having locales generated for them to be able to use them without problems.
Either use service apache2 restart or service nginx restart to fix the problem. In some cases the entire server might need a restart to fix the problem.
Thanks to Helmut Strasser's blog post we were able to identify the problem.