I am very sensitive to caffeine, any drug for that matter so while I love coffee and good tea I cant have as much as I like so my intake is fairly moderate anyway. Estimate no more than 50 to 150mg / day.
I have tried to go cold turkey on caffeine a few times and experienced similar side effects to the OP, not fun at all. The headaches up the back of neck / head are the most unpleasant part - supposedly something to do with blood vessels returning to a more relaxed state / higher flow. These headaches can be so bad as to create nausea.
If I want a break or reduction for a while, I find it much more pleasant (prob healthier to?) with good quality green tea or Oolong, brewing weaker and weaker over the coarse of a week or so. Could just use normal tea as well, but I find green tea to have relaxing qualities to it.
Or there is always no doze, breaking up tabs and slowly tapering off over time.