I prefer to run a distro provided kernel - but this seems to be getting increasingly difficult to deal with as the version of pv-grub Linode uses is ancient.

Amazon EC2 updated their pv-grub a while ago to support some of the more modern compression formats. It would be nice if Linode could do something similar.

It would also be swell if there was another option in the kernel list that made pv-grub look for menu.lst as "(hd0)/grub/menu.lst" instead of "(hd0)/boot/grub/menu.lst".

I keep the root filesystem on an encrypted block device, so I have to put /boot on its own filesystem. If I forget to symlink /boot/boot -> . at install/image creation time, then pv-grub can't find menu.lst and halts.

^ Yes, absolutely annoying to have to install under /boot like that since my /boot mount point isn't part of the root filesystem because it isn't supposed to be mounted 24/7 anyway as per the recommendations of some distros (/boot only ever needs mounted when upgrading kernels)

... With respect to the problem mentioned in the original post, my workaround has been to simply not use any compression when building my kernel since it's pretty much guaranteed to work no matter which pv-grub is installed.