re-deploying the app vs using a patch

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.