Обратил внимание, что на криптохосте не стартует miredo при загрузке. Проблема в том, что на момент старта miredo сеть недоступна и сервис не может отрезолвить прописанный в конфиге сервер.

Начал гуглить. https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=739363 – прошло 4 года. Проблема так и остается нерешенной.

На убунтуфоруме решают костылями в стиле sleep N && service miredo restart. Я решил использовать свой вариант – проверку наличия дефолтного маршрута, который использую на майнинг-ригах (прописать это надо в /etc/rc.local):

while ! $(ip r s | grep -q default) ; do sleep 1 ; done
/usr/sbin/service miredo restart

По-идее, когда мы уже получили дефолтный маршрут (и прочие параметры) от роутера через DHCP, то сеть уже должна точно работать.