I recently upgraded OpenLDAP to 2.4.35 and I'm now experiencing some
instability issues, and also seeing a bazillion of the following error
in my log file:

bdb_dn2id_delete 0x108c68: delete failed: DB_LOCK_DEADLOCK: Locker
killed to resolve a deadlock -30995

I'm using the BDB backend at the moment.  One Google search hit I
found suggested I switch to MDB instead.  Would this help?

mdb (as-is) is not fully stable in 2.4.35, although I can provide you source that fixes the couple of remaining issues it had in that release. It's certainly faster all the way around than BDB for writes and reads for me, and once patched as mentioned, has been stable.