I've never had this issue with any government communication in Germany. Also, all appointments I need can be booked online, so I never had to pay someone for them (wouldn't even come to my mind). Maybe it's more of an issue for particular cities?

Is it safe to assume that you were born in Germany? The system is a lot less friendly to newcomers who have to do everything at once. It's full of catch 22 situations.

That aside, Germany is a federation and every state, city, office and employee adds a layer of variance for a given process.