Where does update-initramfs look for kernel versions?
I had the same problem as you, I also thought I had completely removed the kernel by deleting all its entries in /boot and directory in /lib/modules & updating GRUB, but I found the one directory that is used by update-initramfs to keep track of the kernels:
/var/lib/initramfs-tools