Is it worth even paying for SEO during a Penguin/Panda recovery/cleanup?

First, analyze why you were penalized. DO NOT ASSUME.

If the SEO Company you worked with caused you to crash do you think they'll be able to fix the problem?

If yes, then do so. But if you said no, then cut the ties.

Finding out what happened to your backlinks is #1 in the list of things to check.
#2 is how good is your content in comparison to your competitors?
#3 check if your competition stepped up their game with HQ backlinking and/or content
#4 find out as much as you can about the recent update and work with it

Reassess your site from top to bottom and check out your competitors.
Fix up what you can on your own. Whatever task you cannot manage would be smart to find someone who has the credentials to help. Preferably someone who has done SEO work and has a portfolio of clients that HAVE NOT been penalized by the update.

I agree with TygraOlympia--"If the SEO Company you worked with caused you to crash do you think they'll be able to fix the problem?"
Do not waste any more time mate, and know the real issues.

Why in the heck would you pay the company that screwed you more money to "fix" the problem?

Sounds like they'll produce more garbage results for you and probably do more harm than good.

To answer your original question though, no you shouldn't be doing SEO while doing cleanup. It's counter intuitive and will likely result in having to do more cleanup on the links that you just create.

I recommend removing the over-optimized and crappy links first, that way you've got a solid foundation to move forward from. There are many services that can help you do this such as Google Penalty Recovery & Backlink Removal Service - LinkDelete.com

Finally, after cleaning up the links and getting your profile back to a more natural level then it's time to find a more reputable SEO service or link building service that won't kill your rankings with the next Penguin update, which is right around the corner.

For sure. The last update was pretty much the same as always, more hitting over optimized anchor texts. If you get the right SEO and do your link portfolio well, there's no need to worry.

Also try to find out what caused your penalty.

As once you are penalized by google before starting SEO I think you have to take a look at their portfolio and also to their working techniques. First of all try to find the reason behind your penalty, then you can fix it. Make sure you are not repeating same mistake again.

There's no "SEO WORK DOWN THE DRAIN" in the first place since the mere fact that you got penalized means that the "SEO" work done by that company was risky, lacking in quality and obviously lacking in result.

My suggestion would be to find out what caused the penalty and do as much as you can to remove/fix whatever the issue is before you spend another dime on getting someone to fix anything or else you'll simply just be wasting more money down the drain.

Consider a new site before anything else.

Good chance your SEO company made it only worse.

Penguin penalties are very hard to get rid of and disavowing is no guarantee for success, even if disavowing would be successful you probably won't have a link left to achieve rankings like you had before. That's the biggest problem most deal with, buying links that both ranked you and tanked you.