Prueba de la siguiente forma, la cual en el where le da la condicion que traiga todos los resultados que esperas, pero solo cuando la columna deleted sea igual a vacio, ya que ese valor tendra si esta no fue eliminada(desactivada), saludos.
Código PHP:
Ver originalif(empty($_GET['cat'])) { // traemos listado de TODAS las noticias
$query = "SELECT * FROM `news` WHERE deleted="" ORDER BY id LIMIT ".$inicio.",".$TAMANO_PAGINA;;
}