Pues después de varias pruebas, parece que lo he arrglado con una "," en lugar de "/".
RewriteRule ^([0,9]+)/(\w+)\.html$ index.php?varias=$1&ciudad=$2
RewriteRule ^([a-zA-Z-]+)/(\w+)\.html$ buscar.php?seccion=$1&ciudad=$2
RewriteRule ^([0-9]+)/(\w+)\.html$ buscar.php?tipo=$1&ciudad=$2
RewriteRule ^([a-zA-Z-]+),([a-zA-Z0-9-]+)\.html$ buscar.php?carpetas=$1&ciudad=$2
RewriteRule ^([0-9]+)/([a-zA-Z0-9-]+)\.html$ anuncio.php?anuncio=$1&titulo=$2
Por supuesto también he tenido que cambiar el código php:
El de antes:
<a href="http://www.laweb.es/todos/<?php echo limpiar_especiales($_GET["ciudad"]);?>.html"><?php echo $_GET['ciudad'];?> (<?php echo $registros;?>)</a></h1>
El de ahora:
<a href="http://www.laweb.es/todos,<?php echo limpiar_especiales($_GET["ciudad"]);?>.html"><?php echo $_GET['ciudad'];?> (<?php echo $registros;?>)</a></h1>
Pero sigo sin entender porque funciona de una manera y no de la otra. Por lo visto también influye el orden al colocar las reglas.