This message is not the cause of the delay. It is a comment by some process that looks for a file somewhere called delete and is probably a programming error of some sort, but by the time the message appears the process has already stopped looking for it.
The delay is caused when a partition cannot be found, and is associated with the message "waiting for /dev/sdxn to appear" where x and n are the letter and number of the partition. This might occur before the / partition is mounted and therefore while the kernel is still operating with /boot/initrd.img as the file system.
The remedy, as you say, is to ensure the UUIDs specified in /etc/fstab match the actual UUIDs of the partitions (or specify the partitions in some other way such as a label). However, this applies to both /etc/stab in the / partition and /etc/fstab in initrd.img, which can only be changed by remaking the file to which initrd.img points after making all the other changes. Read the man page on mkinitrd for more details of that.
Hope this helps.