The biggest mistake people are making coming up with these off the cuff suggestions is that the key and fob programing is in the KAM memory dependent on voltage to retain it. In my experience this is not the case. The key and fob information, TMPS sensors, etc are all stored in re-writable memory (for lack of a better term) and no mater how long the battery was disconnected it would all still be there undisturbed. As a flat rate mechanic you need to quickly diagnose the issue or put your family on welfare so I tend to make large passes at diagnostics to eliminate as much as I can quickly. With my limited knowledge of the Honda my first order of business would have been to erase all keys and fobs and reprogram them. My gut says something glitched. It's not a "random" issue the OP has expressed a very specific pattern of failure. I don't want to pretend I know what the OP has done when he goes to the dealer but my experience is that when this weird stuff happens and can't be found it's due to lack of patience from the customer or the mechanics. The mechanics are not interested in losing their ass and spending hours of unpaid time looking for it and the customer needs his car or is overly concerned with the cost and is trying to micromanage the repair. This is a case where dealer management staff needs to step in and figure out how they are going to compensate the mechanic and not charge the customer out the wazoo. Not a lot of dealers are willing to do this. But then again, it's been widely propagandized on this site that Hondas are built by God himself and never have issues so we may be looking at the unicorn of all Hondas to actually have an problem.