In fact I was not correct in stating that it does not work at any new
log-in.... It would be too simple... This is the rule:

My system short date format is reset to be "MM/dd/yyyy", Regional
Options = English (United Kingdom).

If before logging out I change the date to a US format ("MM/dd/yyyy" or
"m-d-yy"), when I login again both the regional settings and excel are
correctly set to MM/dd/yyyy.

If before logging out I change the date to a non US format
("dd/mm/yyyy" or "d-mmm-yy") when I login again the regional settings
read MM/dd/yyyy but excel uses DD/MM/yyyy.

It looks like excel does not like the fact that in our profile we use
UK language with US dates.