Two additional troubleshooting questions:
1) Are you removing the files from the library on the library server itself or on a client PC? If you've been trying to remove from a client, try to remove from the server and see if that makes a difference. Do you have "auto-sync changes" enabled on the client?
2) When you say that in "auto import, the box is checked for 'Ignore files previously removed from library'" do you mean the auto-import settings on the server, or on the client? Try checking the server's auto-import settings to make sure they look how they should. Also try disabling auto-import on the client instance if it's not already disabled.
It sounds as though either your making changes on a client that are not being synced to the server, or (more likely) the server's auto-import settings are not configured the way they should be. If neither one of those is the case, just a hunch, try disabling auto-import on the client (in Options-->Library & Folders-->Auto-Import). I've been seeing some strange behavior somewhat similar to yours when auto-import is enabled on both the server and the client, and since the client shouldn't be importing anything anyway, it can't hurt to disable auto-import on the client (and it may help).