This looks like it was a problem with the VDI's on a network shared storage.
Unpausing the VM's would "start" them but they never actually boot - no console would appear.
In the end, migrating all other VM off the host and then rebooting the host cleared whatever was causing these VMs to be stuck and we were able to delete them
We're currently trialing a new storage provider, so this is definitely something we'll be looking into more with their support.