wheel - 1:59 pm on Nov 9, 2010 (gmt 0)
1) I googled things like "my niche directory" and went searching for really old directories. You can generally tell by looking at them if they're from the 2000 era.
2) I ran xenu link sleuth on the directory(s). This gave me a list of websites that were around back in 2000 or so but are now offline. So I find oldsite1 and oldsite2 that were in my niche but are now offline.
3) I check backlinks for oldsite1 and oldsite2 and find they still has 20 backlinks each. I check each of those 40 sites and fire off an email where I point out the page that has the broken link and ask for a link to my site while they're fixing it.
4) I also check the whois on the two sites. Many are offline but still registered. Some of them are no longer registered. I check the site in archive.org and consider registering it. It has 20 old school links already, I just don't know yet if those links will ever come back. I don't mind registering the domain, throwing up some content and letting it sit for a couple of years either to see if it comes back.
I haven't had a lot of success with this yet but did see some actions, so it can be done - I'm going to continue this week as time permits.