Happens to me all of the time - it's pretty annoying. It would be great if HN used pretty URLs (e.g. http://news.ycombinator.com/news/2 ), or at least URLs that didn't expire.
Obviously it can't remember an infinite number of these, there's a limit, and how quickly you hit that limit probably depends on a combination of how many people are hitting the home page, and how often the order of items in the list is changing.
When HN was younger, you wouldn't see the expired link message that often, as fewer people were hitting the site, and the item order changed less frequently.
At least that's my theory.