Just a thought, but if you have the valves off, try sticking them in a freezer. Like someone said on here before, you could boil them, but it gets much hotter inside the engine, so the carbon is likely to stick on through metal expansion. If you get them frozen it might compress the metal enough that some carbon may break off.
I've never tried this and don't know if it would work or not, but in theory it seems sound.