This is what I ended up using, thanks to Karna's suggestion. I'm posting it as another answer as I am using PHP, so for the benefit of anyone else using PHPUnit and Selenium, here is a similar method to Karna's, but for PHPUnit:
try {
$this->byId('idRemoved');
$this->fail('The element was not deleted.');
} catch (PHPUnit_Extensions_Selenium2TestCase_WebDriverException $e) {
$this->assertEquals(PHPUnit_Extensions_Selenium2TestCase_WebDriverException::NoSuchElement, $e->getCode());
}
The code was taken from line 1070 in the PHPUnit Selenium test code, which I found after Karna pointed me in the right direction.