All these places that offer billing software, don't have what web hosts really need. We need something like the following:

Recurring billing
Discounts on pre payments for 6 months, 1 year, two year, etc.
Ability to charge client for extra bandwidth (2GB over like $8)

What software really does all this?

I would say Ubersmith does all of this.

For the overage part, you could create a new "package" and just make it a one-time fee.

Yes you could do that I'm just trying to find an easier way. I've looked into Ubersmith and it doesn't have all the features I need.

What other features do you need?

One feature I would love is automatic charging if they go over their selected bandwidth.

Oh.

That is A LOT more then a billing program. It would need to be integrated with the control panel. Don't think they have what you need around. If they do, it would be a lot of money.