Error: The method is referenced by Visualforce Page in salesforce.com. Remove the usage and try again

Add a destructiveChangesPre.xml file to your deploy folder and put that VF Page in there and in your package.xml.

The destructiveChangesPre file will remove the VF Page before executing your deployment to get rid of the dependency. After that, the package.xml file will deploy the controller successfully, then deploy the updated VF page.

Salesforce keeps a meta table that tells it which functions are related to other pieces of code, etc. The controller is compiled first, since the page depends on the controller, and as it consults the meta table, it notices that an element that was used in the Visualforce page is now missing.

This halts the entire deployment instead of waiting to see if the element is no longer required. Pages that reference code will prevent changes or deletions to the code that would cause failures. Similarly, pages referenced in code can't be deleted without removing those references.

It would be ideal if they suspended meta table checks until the very end, as it often causes problems in other ways, too, such as trying to delete fields that will no longer be referenced in code, etc.

Multiple deployments are often the only solution. Our last internal release required a total of five deployments to move everything from Sandbox to production, with 30 minutes of unit tests for each phase.