Nuovo problema..
Ho fatto come hai detto tu, ma dovendo aggiungere una nuova regola non va piu nulla, nemmeno quella che avevamo modificato prima:

RewriteEngine On

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d

RewriteRule ^aziende/([^/]+)/([0-9]+) aziende/elenco.php?categoria=$1&pagina=$2 [L]
RewriteRule ^aziende/([^/]+) aziende/elenco.php?categoria=$1 [L]

Mentre prima, dopo la prima modifica che mi hai suggerito era:

RewriteEngine On

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d

RewriteRule ^aziende/([^/]+) aziende/elenco.php?categoria=$1 [L]