Or they are using a wallet which estimates the wrong fee
I have used some wallets that estimate fee wrongly. Even most wallets do that. There are times I will check the mempool and check the reputed wallets, there will be difference in fee estimation, but just little differences. What I know is that even as the wallets estimates fee wrongly, the wallet do not pay very high like that. Likely not because of bitcoin wallet fee estimation algorithm.