There are some pump gasolines (Exxon and BP, I believe) which claim to have additives that will clean up carbon valve deposits. Whether or not this is true I haven't verified. Maybe be worth a try.

-ftyler