The 'maintenance' fee seems like a simple way for them to spread out the costs of... well... maintenance (hydro testing, replacing busted knobs, blown relief valves, whatever). I agree that it only makes sense in the case where they EXCHANGE tanks rather than filling tanks which you must maintain yourself.
Obviously since it's costing them money to take care of the tanks, they're going to recoup that cost somewhere. They could do it by upping the cost of the fill itself, but then I can't imagine it costs them much more to maintain a 20# tank than a 5# tank so it makes more sense in that case to have a flat-rate maintenance fee for all tanks, and keep the price of the fill separate, otherwise the hidden 'maintenance' portion of the fill price would cost you 4 times as much for a 20# vs. a 5# tank.
The 'hazmat' fees are no doubt just fees incurred due to government regulations and such. This probably varies widely from state to state, which could explain why you don't see those fees - or they might just be absorbed into the fill cost.
With all that said, given the fact that the fill prices can very so widely between states (or even between shops in the same state, or even same city) the fill cost itself (not counting surcharges) really does seem to be largely just a crap shoot based on what people will pay - but I still don't think the aforementioned fees are necessarily not legitimate.
