Tesla:
I agree with what you said, and it is good solid advice. In the OPs case, it sounds like the 'sign guy' is long gone.
Without going off on a soap box, what the OP said is a really good example of making sure the permit process is in place. IF the GC had permits, that's a good place to start the search to find him. NJ has a Home Improvement Lic, and for Comm, the GC has to have a Lic. in most (if not all) municipalities. That' no guarantee of getting a sub paid, but it is a starting point to track them down.
I suggest to the 'newbies' to check out anybody they do not know! Established GCs usually have a EC/Plumber/etc. Are they shopping? Talk to the local AHJs, ask them; talk to other ECs, plumbers, HVAC guys; it's like chicken soup; it can't hurt.