I don't blame you. This is turning into more of a headache than it should be.
Since this is intermittent, while unlikely, it may be a hardware problem. First while you are trying to get things working don't plug the Cintiq into a usb hub. Use a usb port directly on the computer.
Are you booting with the Cintiq plugged in? To rule out a hardware problem does the Cintiq work correctly in another release or Distro? Or in another OS such as OSX or Windows?
If you've ruled out hardware the next step is to look at your Xorg.0.log in /var/log. Is it showing you error messages associated with the Cintiq, especially during hot plugging?
You can turn on debugging and generate more messages in the Xorg.0.log. Either in the wacom.conf in xorg.conf.d, see man wacom for the debugging options. Or you can do it using xsetwacom debugging parameters, see man xsetwacom in a terminal.
This is what raises the red flag to me. Maybe you should expand a little more on the xsetwacom commands working intermittently? I assume the Cintiq's display isn't being treated as a separate X screen from the monitor correct? Which means there is a virtual screen composed of both screens. So yes, you would use MapToMonitor to account for the offset of the monitor.
So I fell back to using
xsetwacom to configure the stylus, but often this doesn't
even work (do I need to use MapToOutput to enable this?)
What's the output of xrandr in a terminal? What video chipset are you using?
lspci | grep VGA
sudo lshw -C display