I ride a belt drive bike with a Shimano Nexus SG-C6001-8D IGH. I'm aware of the normal cable adjustment procedure (aligning yellow marks on the hub), I've done this.
When I ride normally, shifting is instantaneous and smooth. However, when I move off at lights, I usually use gear 3, and I've noticed that if I accelerate hard, the hub will not shift into gear 4 after I change it; instead, it only shifts after I go up to 5 (and then it immediately goes 3 -> 5, so gear 4 is effectively skipped over). Sometimes it also happens that if I shift 3->4 and leave it there, without going to 5, 4 will eventually engage after 5 seconds or so.
I should point out I don't attempt to shift under load; I accelerate in gear 3, release pressure on the pedals, then shift and continue.
As said above, this 3->4->5 shifting issue only happens when accelerating. If I ride normally at a constant speed, those gears have no issues.
I know for a fact the shift cable needs to be cleaned, there's likely water inside, as when it was -5°C/23°F outside once, the cable froze in its housing. Could this issue be caused by the cable, or is it a hub problem? I suspect the cable but I'm not sure why everything would be fine when not applying load. For reference, I'd estimate the hub has at most 5000km/3000 miles on it.
A couple months down the road I noticed some squeaks from the shifter lever when changing gears. I sprayed the inside of the shifter with WD40 and in addition to making the shifter work much more smoothly and quietly it also seems to have substantially reduced the problem described in the question. It's still possible to make the hub a bit hesitant about shifting if you apply lots of power directly after shifting, but for the most part, the 3 -> 4 -> 5 changes are smooth even after hard acceleration. Maybe it's because the shifter can now pull the cable more strongly due to the lubrication.