I found out there is actually a builtin function in telescope to fuzzy search in registers. In case someone is interested, I made this binding to access it (lua):
vim.keymap.set('n', 'se', require('telescope.builtin').registers, { desc = '[S]earch r[E]gister' })
I'm not yet sure how to keep the history of deletion though.