MegaMufa

Тыкался, тыкался - разобрался.
Надо было добавить условие для этого правила, что бы оно не всегда выполнялось.

AddDefaultCharset UTF-8
RewriteEngine on
#RewriteBase /

RewriteCond %{REQUEST_URI} ^/storage/(.+)$
RewriteRule ^storage/(.+)$ http://storage.site.com/$1 [R=301,L]

RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . index.php
Options -Indexes

Я выяснил, в чем была проблема.
В файле /etc/apache2/mods-enabled/alias.conf была строка Alias /icons/ "/usr/share/apache2/icons/". Закомментил ее и все заработало.

Раньше директория storage не являлась корневой и ссылки на нее имели вид site.com/storage/icons/1.png. Из-за этого, судя по всему, алиас и не срабатывал.

Теперь ломаю голову: откуда этот алиас там взялся и для чего он был нужен.