I suspect it is common enough that when you observe that praising someone doesn't reinforce their behavior or makes them uncomfortable, you should consider that they might have an unusual aversion to praise.

And also, that you might just be really bad at it. ;-)

This was my problem for quite a while: believing that I ought to praise people, while alieving that there wasn't anything to praise and that they didn't deserve it, due to all their obvious imperfections.

This, as you can imagine, produced sub-optimal results. ;-)