Is it possible to create a reliable billing system with an InDesign XML workflow?

I think you need to make some very rough back-of-the-envelope calculations. Below some rough ideas. Take them with a grain of salt and work it out for yourself. I've not carefully verified my calculations, so I might be far off base here or there. Also, I am ignoring things like occasional crashes, restarts... which can cause things to go slower than expected.

First of all, I'd be thinking of InDesign Server, rather than InDesign. InDesign is not meant for these kinds of tasks. InDesign Server gives you better performance than InDesign can. 

Depending on document complexity, size, script optimization, clock speed, fonts used... you can expect rendering times, say, between 0.1s and 10s per document rendered (just a range of order of magnitude based on my real-life experiences with InDesign Server).

If you need to go faster than can be wrung out via script optimization and optimizing tweaks like using bits of C++ code, you need more instances of InDesign Server working concurrently. 

If you need to process 1,000,000 documents in one single batch, you can expect a single InDesign server instance to take somewhere between 28 hours (a little over a full day), and 2800 hours - 116 days (more days than there are in the month). 

If you need to process 1,000,000 documents, but it can be spread out over the course of a month (e.g. you could process 33,000 documents per day, every day) a single InDesign Server instance could handle simple documents in the most optimistic case (0.1s to process a document).

In the most pessimistic case (10s to process a document), you need 92 hours of rendering time, which means you need at least 4 InDesign Server instances processing concurrently to 'fit' that in 24 hours.

At 10s rendering time per document, a single instance can handle 24*3600/10 = 8640 document renders per 24 hours, so 4 instances handle 34000 documents per 24 hours.

If you need to process 1,000,000 documents in about a single day (e.g. end-of-month), the picture changes.

In the most optimistic case a single instance could handle 24*3600/0.1 = 864,000 documents in 24 hours, so you'd need 2 instances working concurrently to manage 1,000,0000 docs.  

In the most pessimistic case you need 200 instances working concurrently. That'll be expensive, I'd say.

A lot depends on what your expected usage pattern over time is. Also a lot depends on how much can be pre-processed, pre-templated and how complex the documents are. The more variability they have, the more processing it will take. 

All depends. It might be feasible, it might not. Optimizing the process up-front could make or break the feasability.

I would also look into other solutions - e.g. the ones mentioned before, or things like Apache FOP, or custom-made things around iText or PDFBox or other alternatives. 

A lot depends on how high you value good typography as provided by InDesign Server.