I did not read the full post but I can tell you that:
[SERVICE_RELAY_SESSION:S787661:0078db58] Service transaction not found. SERVICESESSION_TAG=15910263
You will get this error and it is not really an error. It is just when there was a packet that was sent out to the network and was pending for a few days, that never hit the handheld and when the BES was rebooted it lost the tag that was in memory, when the BES makes the new connection to RIM you will see a bunch of this coming back from the internet to the BES and since the bes lost the information in the memory from the reboot it spits out this error.
The reason it is not an error because any message that did not get send will get re-queued during the rescan when the bes sees that message has not been delivery to the HH.