I tried pulling the old box apart and most things looked ok, from what I could get to. I stopped when I couldn't tolerate any more cuts on my arms.
My guess is that since the EFI relay controls both the EFI and fuel pump...it had to be related. On the new 100 series versions, the fuse box is much different and has a separate fuel pump relay. Sounds like the engineers realized having that many things on one relay wasn't a great idea.
On most of the immobilizer threads, only one side of the 20A fuse was degraded. On my fuse box, both fuse pin holes were degraded and I had to wire an inline fuse directly to the battery and to the EFI relay to make it work.
I really don't think there's a way to fix a crusty fuse box. Once I had it apart, those connectors inside practically fall out. I guess they COULD be replaced, but it was impossible to take the box apart without breaking it.
I was dreading buying a new box (~$600 for my manufacture date) and was pushing it as far as it could go. When I found the used box for $100 shipped, I had to try it. I knew it needed to be replaced and I was getting other power related CEL codes (P1600 - inadequate power to ECU), so I went for it.
It now starts up quick, every time and I know it's in my head, but it feels like it's just running better. The A/C seems to be stronger as well.