If a node is directly connected to yours via a direct channel then they should be able to see any changes to the fees immediately upon attempting to route through this channel.

However if there is for example a node multiple hops outside of your channels, likely they would need to wait until a route happens through this specific path before they would be able to verify the fee rate you have set.

So if they are directly connected they can query the fee directly by doing channel re-balancing or something like that, if they are not directly connected they need to learn about the fee rate from multi-hop paths.

This is just from my experience though I’m sure there is a better technical answer.