Deleted a MS device from AD before Factory Reset. Now i can't re-enroll device

Can't believe I did this, but I did - and now I would be grateful for some assistance.

In a fit of stupidity I deleted an MS device from Azure AD before performing a factory reset.

Now when I look on the device the MDM account is there in accounts and cannot be removed (policy) and I can't factory reset the phone (policy).

When I try to re-enroll the device I get so far and get the message 

"Something went wrong. Here are some possible reasons:

. Your device is already connected to your organisation.

. Your device is already being managed by an organisation."

I screwed up - how do I make it better?

Thanks in advance

Mark