Yay, it works! Posting my solution:
Just purged nvidia by running:
sudo apt-get remove --purge '^nvidia-.*'

after reinstalling 410 via ppa, the output of dpkg -l | grep -i nvidia is:
ii  bbswitch-dkms                              0.8-3ubuntu1                                 amd64        Interface for toggling the power on NVIDIA Optimus video cards
ii  libcuda1-410                               410.78-0ubuntu0~gpu16.04.1                   amd64        NVIDIA CUDA runtime library
hi  nvidia-410                                 410.78-0ubuntu0~gpu16.04.1                   amd64        NVIDIA binary driver - version 410.78
ii  nvidia-opencl-icd-410                      410.78-0ubuntu0~gpu16.04.1                   amd64        NVIDIA OpenCL ICD
ii  nvidia-prime                               0.8.2                                        amd64        Tools to enable NVIDIA's Prime
ii  nvidia-settings                            418.56-0ubuntu0~gpu16.04.1                   amd64        Tool for configuring the NVIDIA graphics driver

odd that nvidia settings is 418, but anyway it works. Also I used
sudo apt-mark hold nvidia-410

to make sure the driver won’t update with sudo apt-get update.