Roadmap,
I found your "fried" starter relay plug in the archives yesterday from 10/23/2008)

Mine was melted only a little near the red wire which goes to the ignition switch, I traced it in the Honda manual schematic.
I just cleaned the plug connector & blade, the relay seems to be OK.
Do you know what causes this to overheat & melt like that ?
Cheers, Ken