SharePoint site "cannot be imported because its parent does not exist"

I ran a content deployment job from my farm to a farm on another machine. The job failed with the message:

The site /deleteme2/Lists/test1 cannot be imported because its parent does not exist.

Right now I cannot explain why this failed. "DeleteMe2" was a test site that I'd created and subsequently deleted. The site had defintely gone and my farm had no orphaned sites.

To work around the problem, I changed the deployment job so that it only exported a specific site, rather than the entire site collection.

This got me up-and-running and I'll continue to investigate.