I solved the problem by making both 'build & deploy' build configurations write a text file to the deployment folder containing the build type and build number. All tests compare the values in the text file to the current builds snapshot dependencies. If they values are different, re-trigger the build (forcing dependencies to be rebuilt) and then cancel the current build.
Cancel build by calling:
http://teamcity.jetbrains.com/guestAuth/ajax.html?comment=<CommentMessage>&submit=Stop&buildId=<BuildId>&kill
How to trigger build with dependencies set to rebuild:
Is it possible to force a TeamCity build to rebuild dependencies when triggered over HTTP?
This means that when a test is running out of step, the deployment will be re-triggered and then the tests will run.