Digging around some more, it looks like machined stores its data about what vms are running in /var/run/systemd/machines/. This matches what I am seeing in that my dead VM is still listed.
Looking through the code here: https://github.com/systemd/systemd/blob/master/src/machine/machined.c
it further seems like on restart it just iterates /var/run/systemd/machines and re-adds everything to its list.
I guess the strange thing is that there is some mechanism to handle this situation as everything works fine most of the time. In looking through the libvirt code that calls TerminateMachine, I found this bug listed as being worked around in the libvirt code: https://bugs.freedesktop.org/show_bug.cgi?id=68370
Listed as fixed but the original reporter still says he can repro it. I guess maybe my simplest option is to just call terminate on a vm before starting it.
I guess I should mention this is on a rhel 7.2 variant.
If this triggers a light bulb for anyone would be happy to hear about it (or even a pointer if there is a better place to ask about this). Thanks!