welcome to WebmasterWorld, tess161!

what type of server?
what are the technical restrictions preventing you from redirecting?

the soft 404 is problematic and it is likely that google will eventually detect that and treat it as a 404.
even worse if you are showing a soft 404 to the infinite url space and not just the millions of your old urls.
more importantly it is a poor experience for the visitor and the bounce rate will be a signal of low quality that affects your ranking.

the best solution is a 301 redirect to the equivalent new urls (not the home page!)

the next best solution is a 410 Gone response and wait for google to crawl your new url structure and reindex the content.
this will occur faster if you have inbound links, a good site structure and perhaps a good sitemap xml strategy.
of course you will lose any inbound links you had to the old urls if any.
i would also make sure you have custom 404 & 410 pages that actually return a 404/410 status code and have sufficient navigation and search facilities to help visitors that got lost after requesting your old urls.

if you have a lot of link equity to the old urls you should be looking for a solution to bypass your "technical restrictions" and make those valuable old urls redirect to a relevant new url.
whatever the solution it will likely be cheaper than the equivalent link development effort.

Server -
It was IIS earlier, now we've moved to Apache.

Restrictions -
We could not find a feasible way to redirect all the pages, due to ID matching problems in the data bases and so on.

410/soft 404 -
The 410 Gone response is a great suggestion, I will look in to it. We figured soft 404 was better than 404 given our situation.

Inbound Links / Top Pages -
We have 301 redirected all the top back link pages that are available in Google Webmaster reports. These were about 5 to 7 thousand for all sub-domains redirected to their new URLs.

Along with this we mined the top performing pages for the past year & also have 301 redirects in place for them.

Sitemaps -
We have separate xml sitemaps for all types of content - News / Web / Images & Videos. We are banking on these to get us indexed quickly.

Link Development -
There has been no SEO link efforts been put in to the site in recent times and all links have been natural. We knew we will have made damage to our link equity and were ready to take the shot because of our restrictions.

Thanks, You've been Awesome :) -
I never figured the 410 Gone response. Thanks for the suggestion.

If anyone else has a different solution, I'll be happy to know.

Thanks again :)

It would have been very useful if someone had built a table of oldID to newID translations before the new site went live. This could have been used to feed a small script that simply redirected all requests for the old site directly to the new site.

Make sure that the 404 or 410 page on the old site has prominent links to the most popular sections of the new site. At least give people a clear path onwards to where the content really resides.

Could even do it on a category to category basis if page to page isn't practical?

@g1smd Yes, I did suggest this option to have it done via the IDs but with millions of items like image galleries & news items starting from late 90s to present and with completely new data bases to store them, the most we could do was 50,000 URLs as I mentioned above.

Yes, the 404 pages have all the important links, categories, search box etc.

Thanks for you advice :) Appreciate it.

@Marketing Guy

Unfortunately that option was ruled out too.

After loads of discussions, all we got to do in the redirection was 50K Urls with IDs & about 6K to 7K urls with good number of back links & that were most visited in the last year.

Thanks again for your suggestions.

Well, if anyone higher up the chain questions why site traffic is down you have your back covered by having initially advising the correct way to do it. :)

Yes, the drop in traffic and other related consequences were well made aware of. The problem started when the decision to pull down the server that hosts the old files was made.

If the domain name still belongs to you it can be pointed at any server and a redirect system installed there.

A less technical piece of advice - trust the SEO person/team you hired and don't do this type of research yourself at all. The fact you're here describing problems yourself is likely a sign that the SEO has failed (either technically or in communicating) but that may or may not be their fault, it might be yours if you override their decisions and/or change your gameplan midstream etc.

Speak with them and set reasonable goals/timelines, or hire someone new, or just fire them and take over yourself, but not all of the above.