I paid for a tree using presents and the first gift seemed to work fine, the icon appeared on the tree, clicking the tree added a quest to my log and completing the quest gave me the random reward window.
A week later the gift icon appeared again, clicking the tree this time removed the icon but failed to add the quest so I have received nothing this time around.