Jajaja... no sé, la verdad.
Mira, un detalle que se me fue en la explicación es que sólo funciona bien el implode si los índices son numéricos. Si son alfanuméricos, como es tu caso, debes ponerles comillas a todos los valores. De una forma muy bruta

$aLista=array();
foreach($_POST['mis_valores'] as $sVal) {
$aLista[]="'".str_replace("'","\\'",$sVal)."'";
}
$sQuery="DELETE FROM CAT_USERS WHERE str_usr IN (".implode(",",$aLista)")";