Credit Notes are a problem, because if you prevent people from "deleting invoices", then they cannot create a credit note.

Doesn't the Deleted Invoices log meet the requirements? It explains every "missing" invoice number.