Reusing URL of a Deleted Site - is it Possible?

I ask because, although Wordpress doesn't seem to object when I create a new site, re-using the URL of a deleted site, I don't seem to be able to access its homepage. Trying to do so just generates a 404 and that's probably because..

/2011/04/12/3724/

... gets appended to the URL.

In case it's relevant, my custom permalink structure is...

/%postname%/

I am using the directory version of MU, so every site is in a different folder.