Try archive.org I no you can see pages not sure about search results though. There was also a link going around for how google was in 2001. I think that was an accurate search but dunno if you can get 2004 specifically.
I don't believe archive.org / google etc stores results pages. It would give a problem as there are essentially infinite variations. You'd have to set up a scraper / db to do it for you - but no way I'm aware of to get previous results, sorry.
I doubt too you are able to get those results back then, Google algorithm been gone through for so many miles now.
I think having a search engine with old links that is buried under thousands of sites in the search engine, might be a great idea. I too sometimes try to look for links from 2007, but it is no longer to be found anywhere noticeable.
you may use google.com step0: key in keyword step1: http://www.google.com/advanced_search step2: click (Date, usage rights, numeric range, and more) step3: select=> Date: (how recent the page is) => past year step4: click advanced_search Reagrds,