>>So my question is: are
there other paleo people out there grilling their meat?

Yes, with wood only.  Fruitwood, such as cherry or apple smells and tastes the best (to me, anyway).  Wood ash, as I understand, is high in magnesium and other minerals, and I seem to recall reading somewhere long, long ago that some folks used small amounts of wood ash to flavor their meats, or give it a dash of "salt", so to speak.  Perhaps they craved the minerals?  I would assume some of that ash is deposited on wood-grilled meats, especially if covered with a lid for smoking.

I like to char it on the outside to seal in the juices, then leave it mostly red the rest of the way.  I don't care for the taste of charcoaled meat, but I'll eat it and enjoy it, if that's my only choice.

Lois