I'm curious if this started/accelerated when they switched to only accepting super special stamps that only their super special machine can determine whether they're genuine and unused? That would sure be a coincidence.

The fee was increased recently too I believe

This definitely needs investigating properly and determining if we have another Post Office-like scandal on our hands.