I'm a total Linux newbie myself (so perhaps am not the best qualified individual to answer your question), but I recently got ubuntu Linux to boot from a USB stick if it's any help.
There's a couple of issues I encountered however, that I'm not sure you'd be able to overcome (unless you had access to a different PC to help you with this):-
If I remember rightly, you still need to boot into ubuntu Linux (from the ubuntu CD) to be able to partition your USB flash drive into two chunks (one FAT16, one Linux). Seeing as you don't have a CD drive, that's going to be tricky :-) (unless you use a different PC in the first instance)
That being said, you don't *have* to create a Linux partition on the USB stick if you're not interested in "saving changes" to the flash drive (if you know what I mean?). However, you still have to boot into ubuntu at least one time to copy the system files over or something (which is a royal pain in the ass, as you have to connect to the internet through Linux to get hold of the relevant packages)
You need to make sure your computer is able to boot from a USB stick - a lot of older ones won't.
There's a couple of other options, though. ubuntu might be a little tricky to transfer to a stick (although it's smooth sailing to boot once it's done), but it might be possible to run the setup files from a Windows desktop? You'd need to use an ISO extractor or something to get the files out, but it should run from within XP once that's done, I think........
The other option is to perhaps try a different distro or something. Assuming you can boot from a flash drive, the following site is probably ideal for your needs:-
It definitely helped me. I have a feeling you may have already seen the website, but there it is anyway
I haven't tried it yet, but Knoppix looks very straight forward to set up (no need to boot into Linux first)
P.S. I thought the HP utility was useless (all it does it format to FAT16/FAT32 etc, which is pointless as most USB pens are already pre-configured to using those file systems - the issue with the ubuntu setup is that it required a partition using a Linux filesystem, which I don't think the HP utility will do)
Again, if any more knowledgeable Linux users want to chip in and correct me on some/all of the points I just made, feel free to do so (as I don't want to give out inaccurate information)