Solved!

The situation was due to a login script that was changing

HKEY_CURRENT_USER\Control Panel\International\sShortDate

BUT when the sShortDate is modified also other "secondary" keys (not
accessible via the Regional & Language Options dialog) need to be
changed accordingly. When you press "Apply" in the Regional & Language
Options dialog, these "secondary" keys are modified automatically. But
if you change the sShortDate key directly via code, you need to make
sure you also change the "secondary" keys.

In particular the key

HKEY_CURRENT_USER\Control Panel\International\iDate

must be set to 0 for MMDD or 1 for DDMM. This is the key used by excel
to interpret a text date. In my case sShorDate and iDate were not in
sync.