@danwhitehouse: Point of correction: Majestic does not use Yahoo, Bing or Google data; Majestic does its own independent crawl which visits or revisits something like 30 billion URLs a day.
@shadows2000: It sounds as though you are using the historic Index. Try the "Fresh" index which only returns links seen as valid within the last 30 days.
The historic index includes every link they've ever found in several years of crawling and it retains the data even if the links no longer exist. That can be crazy-making for some kinds of research but very useful for other things, such as assessing the longevity of old link campaigns.
FYI I am not associated with Majestic but (1) I have a friend who is, and (2) I subscribe to a tool which is based on the Majestic data set.