Оказался баг студии, конкретнее связки: Instant Run и Build Cache.
Случайно обратил внимание, что уведомление выводится с низким приоритетом IMPORTANCE_MIN, хотя в исходнике стоит IMPORTANCE_DEFAULT. То есть, на устройстве работал старый неактивный код, с когда-то использованным IMPORTANCE_MIN. И, соответственно, уведомление сервиса не выводилось на экран блокировки.
Замечу, что пересборка проекта ни к чему не приводила, так же как и удаление канала уведомления и самого приложения. Instant Run упорно брал из кеша старый мёртвый код с IMPORTANCE_MIN и заливал его на устройство как только что скомпилированный. Причём глючил кеш только на 8.0, что ещё больше запутывало. Короче, помогла только очистка этого кеша.