does appear that they are not ranking in the SERPS
Does that mean the site's not getting any traffic from search engines? If you search for
site:example.com
does it show any pages indexed?
Considering you've got a confirmed Panda issue and possibly other unconfirmed issues ("not ranking") I'd go very careful about this.
The 301 redirect makes a clear association between the penalised domain and the fresh domain. It passes link juice, so theoretically, it can also pass all the nasty things onto the new domain.
A 302 redirect doesn't pass link juice but it still makes the association. (410 for clarity's sake is not a redirect, it simply tells google that the page is gone forever. It's like a 404 status only a more definite one)
So, I'd simply consider the old site a "steep learning curve" and create holding pages programmatically - each page containing a nofollow link to the corresponding page on the fresh domain.
So, for example, if you have example.com/green-widgets.html, this page would now simply say:
We have moved. Please visit us here.
And the "here" bit would have a nofollow link to examplex.com/green-widgets.html
If it's not easy to create these programmatically, you might as well send the visitors to the homepage of the new domain. It's just you'd have a lower bounce rate if you let the visitors click through to the page they've been looking for.
It's worth keeping in mind that dupe content issues might have been caused by wrong site structure, faulty CMS etc. It's important to make sure you don't take these technical issues to the new site.