Did a search and didn't find similar issue so i am posting.
Create and delete a tag.
Paste the expired url.
You will be redirected to a normal page which displays this message -> "No matching items were found."
GWMT returns 404 Soft error.
It's also been reported here http://forum.joomla.org/viewtopic.php?f=712&t=836170
Please if this is already fixed point me to the solution.
Thanks :)