So, it sounds like you're saying the Feds want the provider's contact info, and the Feds collect the fee from them. The user is not involved, as I mistakenly thought. (It's the provider, not the user, who wants Safe Harbor here.)
That still doesn't sound like a restraint on free speech. Governments need contact info from people and organizations in order to function. And occasionally they charge fees for certain services. If the fees aren't excessive, I don't see a problem with them.
Now, if the government tries to influence what content can be removed and what cannot, then I do see a problem.