It seems too much of a co-incidence, but I setup PIO on a laptop recently and found it was using Python 3.7 and was working well.
So I updated my PC to Python 3.7 and ever since then PIO has rebuilt correctly every time…
So is the Python version critical to this issue? Obviously 3.7 is the way of the future…