Eu tive que responder sozinho. Desculpe: (
EDIT: como mchid sugeriu, eu cavei de novo, e percebi que toda vez que eu corro o resolvconf -u ...
/etc/resolvconf/update.d/libc: Warning: /etc/resolv.conf is not a symbolic link to /run/resolvconf/resolv.conf
Então, corrijo-o ligando /run/resolvconf/resolv.conf a /etc/resolv.conf
ln -s /run/resolvconf/resolv.conf /etc/resolv.conf
Testado usando 3 redes sem fio até o momento, sem problemas: D