The Link Status extension (mentioned in an update at http://whattheinternetknowsaboutyou.com/docs/solutions.html) restores a bit of the lost functionality, by adding the time since the link was last visited to the status bar when you hover over the link. It also has on its preferences a checkbox to toggle layout.css.visited_links_enabled if you are using Firefox 3.5.