It sounds like your best bet is going to be digging up some analytics from your old site, finding common URL patterns, and redirecting them more thoroughly via rewrite rules. A clever use of sorting in a spreadsheet can make this task go by much quicker, and if you have some key pages on the new site where you feel entire clusters of old pages can redirect that will help too as you're not redirecting one to one. It would also help to tag the new site's applicable pages with rel=canonical. Lastly, you can apply a nocache tag to the pages on your old site, althugh they should be flushing out fairly soon. Those are the general recs. There is a certain amount of time involved in the process, and it's not a strict number of days/hours/minutes.
Oh, for your 404 page (http://www.structural.net/;flkajhsdlfg) I'd recommend making it a lot more functional, especially since you're expecting a lot of 404 traffic in this current process. Check out Apple's for an example (http://www.apple.com/lkjsfdawe) and this blog post for more ideas: http://www.seomoz.org/blog/personalizing-your-404-error-pages (an oldie, but goodie.)