Symptoms
Initially the symptoms appeared when doing the second deployment of a PandD package. When running through the Analysis, we could see the Workflow Process that was supposed to be deployed to the QA system reported missing references and even if we set it to create new version, during deployment it failed every time. This branched off into two different solutions.
Diagnoses
Unfortunately, there were a few things deleted in the K2 database before we could send this to our Labs team, this caused a few other issues to occur. Specifically, SmartObjects were deleted from the SmartBroker.SmartObject table (in QA) and this eventually caused us to reinstall K2 on the QA environment, creating an entirely new database in the process, in order to get this resolved more quickly. Otherwise this would have taken a lot of troubleshooting and investigation on Labs side (which it did in any case).
We also noticed that this workflow was being started manually in SharePoint 2013, so you had the option of selecting it from a drop-down list and clicking start (in SP2013). However, there was a previous workflow with a different name that we deleted from K2 Workspace / Management Console, however this didn't remove it in SharePoint. In order to remove this reference, we had to delete that specific workflow from a table in the K2 DB.
Please note we backed up the database before making any changes to have a rollback in case something went wrong.
Resolution
So the final resolution to this issue was the following:
After reinstalling K2 on the QA environment, we applied 2 coldfixes: The Package and Deployment rollup for 4.6.9 and the SmartForms rollup for 4.6.9. We applied these on both DEV and QA. After this we packaged and deployed the project's Forms, Views and Workflow in DEV over to QA again. The first deployment worked this time, however subsequent deployments still displayed an error during deployment in PandD on QA.
After investigating further, we noticed that there were 4 GUID's mentioned in the PandD file, one of them being a SmartForms Integration event. So we edited the workflow on DEV, specifically deleted and recreated that SmartForms Integration Event, deployed the workflow, packaged everything up and deployed on QA again. This time we could successfully deploy multiple times on QA (using the option "Create New Version") and this issue is finally resolved.
The main warning everyone should take from this is to never dig around in the K2 database when something goes wrong, because it could lead to many more things breaking (which happened here).