How long does it take to redirect in Google's eyes

It looks like Google never remembers your links and try to find old ones from time to time.
To get rid of old non-existing links you have to demote them using Webmasters Tools under Search Appearance-Site Links. You can do it in bulk using wildcards. Unfortunately it helps only for some time. I can still see old searches from googlebot for links dead for years.

The best way to get rid of old links and avoid them in 404 log of this plugin is hard coding them in .htaccess

301 redirect doesn’t help. In fact Google says, that 404 error won’t harm your site ranking.

It looks like 301 redirect is only useful for your customers having old bookmarks and for some transition period until googlebot realizes your link has been gone and replaces it with fresh copy.