Comment 9 for bug 1527710

Wouldn't this change be causing the issue?

update-notifier (3.164) xenial; urgency=medium
  ...
  * debian/99update-notifier:
    - Now additionally triggers the an asynchronous background update of the
      cached info via update-motd-updates-available hooking into
      APT::Update::Post-Invoke-Success.

Here's the contents of 99update-notifier:

  1 DPkg::Post-Invoke {"if [ -d /var/lib/update-notifier ]; then touch /var/lib/update-notifier/dpkg-run-stamp; fi";};
  2 APT::Update::Post-Invoke-Success {"/usr/lib/update-notifier/update-motd-updates-available 2>/dev/null || true";};