Stuff I've looked at:
Mojopac - Comes with your own virtual desktop and is easy to use, but ONLY WORKS FOR XP 32BIT WTF
Ceedo - Looks the most promising, but reviewers have complained that its custom setup component is worthless
Prayaya - Crappily packaged Chinese Ceedo clone
U3 - Only works with U3 flash drives, doesn't completely virtualize the app (stuff is written to the host comp)
VMWare ThinApp - I trust VMWare to have really good compatibility, but the whole process of using a clean-installed OS to setup apps seems like a pain
Xenocode - Haven't found it on Bittorrent, so

Do you guys have any recommendations?