...there was no backup of it, hence a holding page. Only way I got some of the old content was through the internet archive from a cached version of about 2-3 years old.
That's a difficult situation, and it sounds like you gave it the best shot by going to the Internet Archive.
I would do backlink searches on one of the available backlink databases asap. Depending on how long the site was down, a "recent" link search might not do you much good, so you'd want to look at the historical backlink data. Also monitor your server logs for 404s.
Do not simply redirect all broken backlinks or external requests to the home page. You want to 301 redirect the most appropriate old TargetURLs to the most appropriate new TargetURLs. Since you won't necessarily know what kind of content was on the old target pages, you'll have to do some detective work.
Start with your most valuable backlinks, as weighted by the backlink database, and check the data to get a sense of what was being requested. Checking the SourceURLs might give you a clue. If your old Target URLs were descriptive in terms of content, and/or if there was a pattern to them, then you are in luck.
In checking 404s in your logs, do your best to make sure that those urls returning 404s actually existed. Googlebot is known to request nonsense (like unlinked urls) in an attempt to find new content and test various. You may get requests from a lot of bots with query strings on them. Forget about those... let them continue to return 404s.
Monitor your logs for "good" 404s on an ongoing basis. The most valuable 404s are going to be those which were actual user requests rather than from bots. 301 those urls which return 404s to your most closely matching pages on the new site.
Try to get the highest quality links redirected to the most appropriate new pages as quickly as possible. In cases where you know what the page matches were, redirect them and then try to contact webmasters of linking sites and get the links updated at their end.
Sites I've worked on that have been down for several months have revived, with rankings back, within a few days to a week after links were restored... but none of these were cases where we also needed to redirect. Those will most likely take longer to come back.
If the linking sites change their broken outbound links before you've redirected them, then you'll be out of luck, so get on this with all possible speed.
