What is attainable WOT now compared to the spec WOT range? Are you reaching near the high end or just can't get past 3600RPM ? Repitching is usually up to 2" max from the original specs since they can't change the root, so it's possible you really need another set of even lower pitched props. You did have them LOWER the pitch , not raise it , and confirmed results, correct? Just checking....
Is there possibly a T/D sticking out ahead of the cavitating prop?
Are you making good use of tabs to reduce the prop load as well as reduce chance of entrained-air flow past the props?
Hopefully you had the prop work done at a PropScan or MRI shop so, as Vic mentions above, you have a before and after scan printout confirming intial condition, work done and present condition to least ISO 1 spec., and can also see the props were matched ( final average pitch , dia, #cup).
It's always possible the prop was damaged after service/ before it was installed on the boat -happens all to easily. Few yard techs are going to reveal they dropped the prop and the change could be unnoticeable by quick visual check. You never know...
Also, just because they were just serviced doesn't mean they couldn't have grounded or hit flotsam on the maiden run.