What I've discovered is that if I specify an AppDomain in the BizTalk
config file, and assign the relevant assembly to that AppDomain, and
set the "SecondsIdleBeforeShutdown" and "SecondsEmptyBeforeShutdown"
to -1, then the restart problem goes away!

So, I have deduced that in the default configuration, the AppDomain is
unloaded after 30 minutes.  And for some reason, loading (or
creating?) a new AppDomain fails the first time around.  Or the
orchestration fails to get loaded into it.  Or something.

But I've read somewhere that the default AppDomain is set to NEVER
unload.  My BizTalk Application *is* running under a new Host Instance
(with default configuration).  Could that be an issue?

If I don't specify any AppDomain information in my BizTalk configure file, what are the default values?

Even if the AppDomain *is* unloaded, why would I get an error/restart when the next message comes through?

In fact the problem I had was that I got an invalid cast exception, the AppDomain of the BTSNTSvc.exe process was different from the AppDomain of the loaded assembly, eventhough the two types were
exactly the same, since they were in two different AppDomains there was this invalid cast exception.
Since I had a work around making all the values in the AppSetting Section solved the problem, it would have been nice to open a case to Microsoft to understand why there was this issue of loading an
assembly in an other AppDomain, but since the work around worked better no case was open and I could not give an explanation