While on Tomcat 6 and Eclipse Ganymede I found out the following chain to work like charm:
1 stop server
2 project -> clean
3 project build (I had automatic build disabled)
4 delete server
5 delete Servers folder
6 restart Eclipse
7 create new server, add project and start :)