Hi, I've been suffering with this issue since iOS 13 came out as well. The first symptom was my Apple Watch randomly running the battery down for no reason during the day. Then I started to notice having to complete reminders on multiple devices, and finally, they started showing up late or not at all. On my Macs, I've occasionally found the process remindd running at 100% CPU, which I assume is also happening on my watch, leading to the aforementioned battery drain.
At one point I used my Mac to delete all completed reminders as I too have thousands (WHY are these saved? Why is there no option to auto delete after a week, or not save them at all?) However, this deletion never synced to my phone, despite me turning off iCloud reminders on my phone months ago and then turning it back on. I am now using iOnAsJ's link just above to delete all 2930 reminders with Shortcuts and that, at least, seems to be working. But it's evident that my devices aren't syncing since "show completed" on my Mac only shows the ones since I did the full delete on the Mac months ago.
All devices are running the most recent non-beta releases of their respective OSes. I agree that it "feels" like something is broken in our iCloud accounts, but I have no way to analyze that further. We should probably all file bug reports or contact support. I recommend doing that after iOS 14 ships with no fix for this issue, otherwise they will simply ignore the bug and ask us to try it with 14.