By live CD you mean something like running a .iso or an install disk? (Could I do this on a virtual machine then delete it?)
I am currently looking over vanitygen, I like it, never knew how people got the "special" addresses.
I'll post here again with some more questions when it comes do doing this.
Once I get the private key from vanitygen, how do I go about accessing my coins again?
Using a live CD is basically theatrics. The way it works is that you download and burn a CD/DVD using your primary OS installation and then boot off that. If your primary installation is compromised then the live CD can also not be trusted. So what's the point?
Using a VM is even worse. If the host system is compromised a VM can also be compromised.
Actually there is no way to do this without touching the Internet. Even if you decide to dedicate an entire computer as your offline wallet PC you will still need to connect to download the OS and bitcoin wallet/client software. If you are using Linux on your "offline" PC you will need to connect regularly to update software or end up in dependency hell.