SharePoint Online - delete from a list via rest api in batch mode

I'm adding and removing items in a list on SharePoint online MS 365 via rest api in batch mode. Everything was working fine till last week. I started to get "HRESULT: 0x80131904" errors for some items in the batch when deleting. I got this error just for some items not for all items. In other words when I send a batch of 100 items, system deletes around 50 of it and give above error for the rest. This is true just for deletes, I have no problem with batch adding. I further investigate the issue and realized that if I just send a single batch of what ever size(I know max limit is 1000) I never get an error and system deletes the items in that batch completely. But if send multiple simultaneous batches I got this error. That is when I sent batches consecutively at the same time I face this error. As I said this was working till previous week. What might be change on the server side since I did not made any changes on my side? Any help will be much appreciated.

Additional details:

• My list size is around 8K items.
• Its storage size is less then 10 MB.
• Every hour periodically I insert new 8K items and that makes my list size around 16K items
• As soon as adding process completes I delete the previous 8K items again every hour