Ensure all backend methods respect deleted domains

Change-Id: Iabaf990309e7f9950e61a763176d3d4ada90a8c4