How to do SEO of large directory webiste?

[iisark]

Hello,
My name is Ivo Petrov and I'm junior SEO specialist. I have optimised few websites in the past, but now we have to deal with much bigger project. We need to optimize a custom made UK business directory (like Thomson Local). I need advice from more experienced SEO's on how to do the advertising campaign. Here are my questions:

Question 1:
Should we submit the site to many local directories?
I don't mean fly by night directories,but high quality onces? I heard that directory submission is not a good practice anymore but since these are most relevant websites we are planning to use them in our campaign. Is that a right move?

Question 2:

How many links the website needs to rank in Search Engines? Our main problem is that the site has thousands of pages ( e.g. categories, locations, lisitngs..) so i need a rough estimate on how many backlinks are needed to rank most of these pages?

Question 3:

Is that a lost cause? I know that the directory is a quality website but is there any chance at all to beat the Big Boys? This is my first project of this size and i feel a bit scared. We are only 3 SEO's in our team and not sure if we can handle such a large task. I need to know what to say to my employer.

Thank you in advance for your help and will wait for your advices.

[PixelatedKarma]

Here is how we've tackled large website SEO in the past:
1)Inventory all of your potential quality links
2)Rank these links and organize them by highest quality and by their relevancy
3)All of your general high quality links/web 2.0 links/etc. you want to tie directly to your main page.
4)All of your niche high quality links you want to build to each corresponding category. So lets say you have a technology directory within that site; you'd for example build a link from a website like daniweb to that technology directory. By treating each specific directory within the site as a landing page you can also seo each of these sub-directories as you would a landing page on a smaller website.
5)Dont forget your CTAs and content which refreshes on your main directory page / sub directories - this will help you get crawled more often.
6)When you've done your major link building; focus a different sub-directory every week; lets say Beauty Products and Services is one of them....When you are browsing the web looking for links you can then focus on doing quality posts on forums going "hey if you are looking for quality haircuts go to insert directory page link for the company here.
7)Use bit.ly or another service when submitting content/site links to some of the lower reputation websites (mR 2.9-4.5) as this weird little thing happens where using these services will not just help you gain traffic measurements to know what is working and actually bringing you in traffic but it will also improve the quality of the incoming link by scrubbing off some of the low reputation you are drawing from.

I know people will argue # 7 and say dont go after lower quality links - however if they are a new website for example that is relevant they might not have enough mozTrust to have a decent mozRank or maybe they are a high traffic website in the same niche but because of their own low quality referred traffic they have a low mozTrust rating. That doesn't mean that the sites are useless just that you do need to be careful and scrub them down alittle bit. End of the day if you are a match made in heaven with that site regardless of its rating; SEs will see that the referred traffic has a low bounce rate because the people being referred are finding what they are looking for which is a great signal to the SE that that link is providing quality to visitors.
8)Lastly watch your automated links on directory pages themselves; I know it sounds silly but you are probably going to want to either have the site owner manually approve directory listings or automatically give nofollow links back to pages. This still gives them some link juice without losing yours.

There are a million more tips; and you should probably take the next week to google directory seo guides and tutorials. Alot of the information will be out of date though but there are some good things out there geared specifically to directories. Your best friend is going to become metrics - by studying your metrics you will find out what is working and what isnt.

ALSO
Dont make promises to the site owner you can't keep; if this directory is of decent size - dont tell him/her it'll take 3 months cause it'll probably turn into a year long project with a team that size. This will result in an angry customer who is over budget and/or an angry customer who isn't paying you guys what you need to be a successful company.