We have a TFS Server, but whenever I create a file and afterwards try to undo the addition, TFS doesn't delete the local version. I already tried to reassign the workspace, completely delete the workspace and re-download, check the workspace bindings and so on, but nothing worked so far.
You may mix up something. For TFVC source control, when you are trying to "add" files to TFS, it creates an entry in the database just waiting for the files. Instead, undo your "add."
Right click on any source file in the source explorer, and choose Undo Pending Changes. Click OK to undo those changes.
That will clean up everything in the TFS database. However it will keep the local files, since they are actually not checked in TFS server and do not have any mapping relationship. Operation in the server side definitely will not affect local files.
If you want to make sure your local folders and server folders are the same, you could also consider to use reconcile differences between two folders, take a look at this link.