tedster - 1:52 pm on Mar 15, 2012 (gmt 0)
Matt Cutts has said several times that Google prefers to receive a 301 redirect in every case of a address for content (and 410 Gone if it's completely removed).
However, my experience with clients who did redesigns has been better when we only cherry pick the important URLs for 301 treatment. In this case "important" means strong backlinks and common direct entry pages. The rest we let be 410 and Google seemed to crunch up new rankings a lot faster that way.
However, you are also dealing with Panda so my past experiences are not exactly parallel.