Have a large amount of junk contacts that are not part of any data extensions that need to be deleted (400k) from the marketing cloud instance. What is the easiest way to go about doing this? If there is an option to delete all contacts and start with a fresh instance this is also an option we are considering.
To delete a large volume of contacts like this, you could query (or import) these records into a data extension and then call the REST API to delete all contacts within that data extension. Here's the endpoint for doing that.
This would only remove these records from sendable data extensions, in addition to deleting their contact information across channels in your account, so you'd need an additional process to remove these records from any other data extensions that they may be in. You can find an example here that could also be modified pretty easily to perform the delete w/ WS Proxy or suit any other requirements you have.