CLN is doing some improvement, do you have the last version? They do some work related with that in this one https://github.com/ElementsProject/lightning/releases/tag/v25.02
I noted that "many" nodes are setting some high fees, for example... I think that 1500ppm could go through without issues, but if you set it in the order of 300ppm or less it's going to fail a lot. What ppm are you using? do you use some MPP (multipath payment) configuration?