Yikes... I had the worst time finding your post. You responded to it this morning, it no longer shows up in the "zero reply threads"... But obviously I found it.
What you are facing is Grub2 (vs Legacy Grub). Most of the documentation that you run into is for Legacy Grub (0.95, 0.96, or 0.97). As you learned, Grub2 uses a suite of files to build its grub.cfg. Once you make changes to any of those /etc/grub.d/ config files you need to run /usr/sbin/update-grub, which is a shell around
Code:
exec grub-mkconfig -o /boot/grub/grub.cfg "$@"
which you alluded to ("mkgrubconfig or something like that").
I'm new to Grub2 (I recently installed Ubuntu Netbook Remix on an HP Mini), so I don't have a lot of experience. But you can remove the "20_memtest86+" file from /etc/grub.d, run update-grub will rebuild grub.conf, and viola no more memtest entry.
I don't know what happens when you put maintenance onto the system. Will the "20_memtest86+" file reappear at some point? Does the system retain your other changes? If no one else comments on this, post a short question on just this topic and someone with more experience with Grub2 will probably respond.
In reference to your experience with UUID's, they seem to be the wave of the future. It's usually easiest to go with what's popular with your distro. UUID in my experience works well.