Thanks for the extra details. This is really peculiar. I'm running Ubuntu 16.04 locally and couldn't reproduce it. I see no +cgroup entries when creating exec or docker jobs. Same with the Ubuntu 16.04 vagrant in the root of the Nomad repo.
Do you have any custom udev rules installed or any container/virtualization related packages installed that may have added rules that create these cgroup entries?
Do you have any systemd updates available on this system? Since it seems like these entries are being improperly leaked (since you can fix everything by running cleanup), I'm wondering if there's just a bug that's been fixed on my systems.