Невероятно, но техподдержка ВКонтакте подсказала верное решение:
надо mime тип заменить на другой, не image, не video и не audio. Например, на application/vnd.my.package.
Тогда передаваемый gif файл сохраняется в Документы пользователя и отправляется сообщением
