Honestly I don't think it's super rare. We have several hundred AUTO debits on our various cards per month for incredibly large dollar amounts, and if two vendors bill at the wrong time or we purchase extra equipment one month, it can max out credit by accident and then we have to use a different card or pay off the card and wait 24 hours. We typically pay off all of our cards once per week to keep the balances low. Small charges like credit refills aren't an issue, but the larger monthly charge could be a problem if something else goes through on the same day before.
Several of our clients have this issue as well. I think it depends on what kind of transactions you're putting on your credit card. Companies that pay mostly via check don't have issues like this, but companies like ours that put everything humanly possible on a credit card will run into more issues, even if we have the cash in the bank.