When I started consulting, I initially made the date part of the invoice number, e.g., 04100501 was the first invoice sent on October 5th of 2004. This sidestepped the problem of showing customers how many invoices I had already sent. But it did show them how many I sent that day, which was usually not many.
I eventually switched to a sequential monotonic invoice numbering scheme for other reasons, mostly because it made it easier on the webapp I use for invoicing.
yymmdd<seq-#> is monotonically increasing. Though you could also just combine the first 6 or so digits of unix time and tack on a sequence number to the end of that.
I eventually switched to a sequential monotonic invoice numbering scheme for other reasons, mostly because it made it easier on the webapp I use for invoicing.