In my case, I found the culprit and also found how to reproduce the issue.

The culprit was that my servlet opened files by using the Scanner class and neglected to use Scanner.close after reading the files. The files being opened were ones in WEB-INF/classes and hence tomcat's undeploy operation couldn't delete the contents of the WEB-INF/classes folder.

Here's the scenario to reproduce the issue (before fixing it by adding calls to Scanner.close):

1. Stop and restart tomcat
2. Copy my war file to webapps to force redeployment.
3. Run my servlet twice by invoking its url from the browser.
4. Copy war file to webapps again to force another redeployment. This is when the issue occurred.

After adding Scanner.close invocation, the above scenario no longer has any issues.