I have a third party DDE app that exports dates as strings, correctly
using the short date format in the regional and language settings,
which, in my case is MM/DD/YYYY (reset at every boot).

Unfortunately excel insists in interpreting that date as DD/MM/YYYY
[Application.International(xlDateOrder)=1, it should be 0],
disregarding my regional settings. The result is that all the dates are
wrong or #VALUES!

If this is not wierd enough, listen to this: it only happens after I
reboot (when the date format is reset to MM/DD/YYYY). If subsequently I
change the short date format in the regional settings to something
different and then back to MM/DD/YYYY (exactly what it was when I
booted) and restart excel, it now uses the correct date format. So it
looks like excel is not reading correctly the regional settings at boot
time.

Since I need to distribute the spreadsheet (with the DDE link), I
cannot make assumption about the regional settings of the clients. The
third party application does not give any problem, if excel worked as
expected the two should be in sync as far as date formatting goes...
I'd appreciate some insight.

To replicate the problem, create a spreadsheet with a macro

public sub checkDateFmt()
select case Application.International(xlDateOrder)
case 0
msgbox "MMDD"
case 1
msgbox "DDMM"
case else
msgbox "Other"
end select
end sub

Run the macro and check against your regional settings.