I think restricting yourself to 32-bit counters is fine (it's also an issue of memory overhead as you have one of these per access to a global, and per dictionary); you have to deal with the overflow, though. I suggest to use an unsigned value, e.g. size_t.

Overflowing should be dealt with through visiting all objects, as you say. It could either happen right when it overflows, or it could get integrated into GC, and only reset when the GC runs. You'd then need to account for those periods when it already has overflowed, but GC hasn't run yet; in these periods, counting should be "on hold".