I think it's the non-linear processes that have trouble with the back button. Clicking back should go to the last modal state. If your app is fundamentally non-modal, then the last state is outside your app and clicking back should exit (after persisting all state, of course).

But most apps can be broken into at least a few states. For any document based app, like Photoshop, navigation should probably move between document views. Any modal dialogs should be closable with the back button. You don't have to use it for everything, it just has to do something sensible and non-destructive at any given time.