How pervasive is this problem. Can you indicate whether it affects the following:

• Links in search engine results pages?

• Search results from the Firefox search box?

• Search results from the address bar?

• Sites you access by typing their domain in the address bar (e.g., google.com)?

• Sites you access using a bookmark?

If we can narrow it down, we might spot the pattern.

If you don't have a lot of patience for troubleshooting, you could try the new Reset feature. This duplicates certain key data from your active settings folder into a new one, bypassing some add-ons and custom settings. Your plugins will still be active.

More information in this article: Refresh Firefox - reset add-ons and settings.

If the new settings folder has the same problem, you can switch back if you like using Firefox's Profile Manager. (This article describes how to start Firefox in the profile manager. I do not recommend removing anything until you are 110% certain that you will never need any of that profile's data in the future. Profile Manager - Create, remove or switch Firefox profiles)

Does it make any difference?

This can be caused by corrupted cookies.

Clear the cache and the cookies from sites that cause problems.

"Clear the Cache":

• Tools > Options > Advanced > Network > Cached Web Content: "Clear Now"

"Remove Cookies" from sites causing problems:

• Tools > Options > Privacy > Cookies: "Show Cookies"

If clearing cookies doesn't work then it is possible that the file cookies.sqlite that stores the cookies is corrupted.
Rename (or delete) cookies.sqlite (cookies.sqlite.old) and delete other present cookie files like cookies.sqlite-journal in the Firefox Profile Folder in case the file cookies.sqlite got corrupted.

See also:

• http://kb.mozillazine.org/Cookies