Yes, "deed" would be appropriate in that sentence.
I do think sometimes we just have to memorize a way of saying something. But I usually try to change how I think about it so I'm more familiar with the Russian frame of mind.I think the problem of choosing the proper preposition in “to remind of” and ”to be proud of” is very much similar to one of choosing the proper case of a noun after a verb in Russian. I mean your question about using the instrumental instead of the accusative. The answer in both cases is “Just memorize and use this way.” Don’t you think?