So what do we do if some third party app has rendered our iPhones unusable or we simply want to start a new.

Obviously the simplest answer is uninstall the app.
However, does this leave garbage files on the iPhone? From what I know it does...each application still leaves some traces of itself behind.

The extreme case?
Would require us to restore our phones to the original firmware. But what about us unlocked users? Do we need to virginize once again? Or is it a simple matter of restore and unlock/jailbreak?