To clarify:
the NRMP does not require you to have an ECFMG certificate to apply to the match, only to have:
1) all your exams and paperwork (with the exception of the final diploma) completed by the time that the rank order list is due
the RRC requires you to have your ECFMG certificate to START residency.
HOWEVER, individual programs can make up whatever rules they like. If they want you to have your ECFMG certificate to apply, they can make that a rule. As noted above, the program takes a chance ranking and potentially matching you if you don't have your certificate - after all, it might not be awarded, you can't start residency and they have an open spot on July 1.
This is not common however, and should not prevent you from finding programs that will accept your application without the certificate. Better safe than sorry, if you can get it before the match, great...but it is not required by NRMP or most residency programs.
FYI - california has its own rules (including the infamous California letter and USC is a big name school, so they can afford to be picky).