An aspect of the invention includes a method for receiving a request to reclaim a portion of a memory assigned to a virtual machine (VM). In response to receiving the request, an increment of the plurality of increments to vacate is selected. The selecting is based at least in part on the failure counts corresponding to each of the plurality of increments. An attempt is made to vacate all contents of the selected increment. Based at least in part on determining that all contents of the selected increment were not vacated, a failure count corresponding to the selected increment is incremented. Based at least in part on determining that all contents of the selected increment were vacated, an assignment of the selected increment to the VM is removed.