In short, I've found a bug in Puppet running on Windows that, when fixed, made our catalogs apply about 10 times faster. See PUP-9092 for details and puppet#7033 for the fix.
It appears it was an oversight instead of an error, but still... having catalog applied in 31 seconds instead of 320 is very satisfying. Hope it being fixed in official Puppet releases soon, so we don't have to keep patched version installed.
P.S. I had to take a look at it sooner, I swear, it only took about 10 minutes to find the root cause, but it always seemed less important than other things.