I'm sorry I have to say this, but I think your opponent missplayed this a lot and Rebuild should normally win this.
When the Duchies were gone an he had 4 Estates in his deck, he should have stopped naming Province and named Estate instead. That way the game would have ended before you had a chance to catch up.
I really don't get why he switched to naming Duchy on turn 18/20, which made him trash his estates for nothing instead of piling out the Provinces.