Yep, the limit will be for
max_doc since Lucene internally uses an integer id to refer to each document. Because deleted documents are soft_deletes, it still needs to have an id assigned to them to be able to know which are the deleted documents.
A solution to your issue could be to start indexing into a new index and use an alias to be able to refer to both the new and existing index as if they were 1 index. This would avoid you needing to re-index all the existing data. Given that at that point the existing index would be rarely accessed you could then optimize the existing index to remove the deleted documents entirely. The downside here is that if you still need to be able to delete documents from the existing index you will need whatever is indexing the content to be aware of both indexes and to delete the document from the correct index.