If it's genuine, it won't tend to come across as patronizing. Think of it less as "making someone feel 'appreciated'" and more "give credit where credit is due".

After all, you can't force someone to feel a way, you can only control your actions. If someone has some issue where they distrust even genuine expression of appreciation, that's on them to work on.