The main weakness in this sort of registration is that anyone can submit a work which they claim to have authored, and the companies take such submissions at face value. This is in contrast to most jurisdictions where a state-run registration service exists (USA, India etc), where official registration is prima facie evidence of copyright ownership (see for instance § 410(c) of the US Copyright Act).
Surely a state facllty has the same issue - i.e. anyone can submit a work which they claim to have authored to a state facility.
An equally effective way of establishing that a work existed at a particular point in time is to put a copy of the work in a well-sealed envelope and post it back to yourself and retain the proof of posting as well as the unopened envelope bearing the date of posting. The envelope should only be opened when it is necessary to prove that the work existed at a particular date, for instance in litigation, when it should be done in the presence of witnesses who can attest to the unopened state of the envelope and that the contents accord with the claim. As for establishing that you are the author of a work, the best approach is to arrange for affadavits (formal sworn statements) to be made by anyone who witnessed the creation of the work or who can reasonably state that they know that you created the work. If there are any preparatory drafts, recordings, sketches or data files of the work, these should also be stored carefully as corroboration of your claim. Resist the temptation to go back and add a date to an old document as this could amount to forgery and would undermine your claim if discovered later.
I think a registration company does have an advantage over the 'post it to yourself' option. As they are storing it for you, they represent independent (that is to say independent to you) evidence that the content was in your possession at that date.
Posting to yourself, also know as "poor man's copyright", seems to be widely scorned by many (just did a Google search). If you have an old envelope lying around, it is pretty easy to put something in it today, seal it, and claim you posted it to yourself on the postmark date, so having some independent source of evidence certainly trumps that. I have loads of old envelopes with documents in from various companies, etc. in my filing cabinet so faking would be easy for me.
As Andy says these companies seem legitimate. What they do is simply witness the date and content of your work; which in my view is better than doing nothing or posting to yourself, but you need to make your own decision whether that has a value to you greater than whatever fee they are charging for their services.
I agree with your point about affidavits, but that only helps if there is someone who can swear that they witnessed your creation of the work and can remember what the work consisted of - I don't think even my closest friends know what I am working on most of the time so I for one would be stuck. Having a work independently witnessed by one of these companies is certainly better than doing nothing or simply posting to yourself if you have no other means to establish evidence of your claim on the work.
The point about keeping preparatory drafts, etc. is a good one. This shows evidence of the evolution of the work over time. When I write code, I use a version control system that tracks the changes to code over time; which is a good thing to have as there is a clear record of the changes and evolution of projects over time.
Not sure if that would appropriate to you, but the version control system I use is called 'git' if you want to investigate that option.