Are all advertised registration services legitimate?

To answer your title question:

Yes, and No. Only registrars accredited by the Internet Corporation for Assigned Names and Numbers (ICANN) are authorized to register .com, .net and .org names in the registry.

Some of these accredited registrars offer their services through resellers, which may provide assistance in completing the registration process. Your registration contract, however, will be with the accredited registrar and that registrar will maintain your contact information. Although many resellers are not accredited registrars themselves, they are resellers for accredited registrars and thus are legitmate.