When should we re-deploy an application vs. using a patch?
Discussion posts and replies are publicly visible
You should deploy the application only first time and then every time after that, you should only deploy patches. I guess you're working on an older version because patches do not exist anymore. Appain introduced applications in exchange for packages.
It depends on a lot of factors. Is the overall size of the application large? Are only a few of its objects changed? Do you want to deploy all changed objects or only a targeted subset? Are there patches/packages created? The answers to any of these questions can change your deployment strategy on an application-by-application basis.