Does this happen to you on various different web sites or only on a particular one? My suspicion would be that you are visiting a site which generates the target of the link dynamically. While the link still appears to be the same and behaves the same, if the URL is not exactly identical, it will not be matched to your history by Firefox.

I recommend that you copy/paste the link right-click "copy link location" into a simple text editor of your choice (e.g. Notepad), and do the same again after refreshing the page. I expect you will find that the links are not pointing to the same URL. Then it is a consequence of the site you are using, and can't be avoided easily. Ask the site's support for any hints on what to do. For example, if you disabled cookies, some sites will alternatively append a unique string to the end of each URL, and by enabling cookies from that site you could change that behaviour.

If the URLs really are the same, please report all add-ons you are using as they might interfere with the mechanism. You could in turn disable some add-ons and check if that makes a difference. I find it very unlikely that this mechanism is generally broken for you, as it is a very basic functionality of browsers, including Firefox, and works well for me any many other users.

Thanks, I figured it out now! One of my extensions was changing the links I visit.