I deleted a product for good and have nothing to replace it with. What should its old link do?

Use a Gone (410) redirect. It tells search engines the page has been removed for good, which drops it from search faster than a normal 404.

1. Go to SEO Settings → Redirects (part of the Advanced SEO plugin).
2. Under Add a redirect, enter the Old path, for example /product/old-name. You can paste the whole URL and only the path is kept.
3. Under Type, choose Gone (410). The New path box is then not needed, because there is nowhere to send anyone.
4. Click Add redirect.

If you later add a similar product, delete that rule and add a Permanent (301) one that points to the new product instead.