Firstly, I'd try to not run tests on true production databases if possible, but I know this cannot always be avoided.
In my tests of this type, I ensure the database is as expected with a range of simple AddEntry, DeleteEntry, AssertEntry and AssertEntryCount routines that either insert, delete, assert the content of, or assert the expected count of rows in tables with specified fields and values.
These have a TableName parameter and then a ParamArray parameter called ColumnsAndValuesAndOptionalConnectString (as well as a couple of straight SQL query overloads) that expects field names, then the same number of values and finally an optional connection string.
In your case, I'd have one (or as few as possible) test that creates a new user and if it succeeds the cleanup does actually drop the user created.
The rest should refer to a single (or again as few as possible) "Integration Testing" user that is normally marked as deleted, but that user is undeleted while tests are performed upon it.
To answer your question: "Should I provide a way to really delete a user?" If you don't want to access the database directly to "run delete queries against it", you have to choose between creating new test users for every test or creating some code path that actually deletes users. If you do go for the second option you can make the user deletion routine only available to your test code by a number of means, and depending upon your development environment, you may be able to avoid showing it on your public API.
Perhaps the most straightforward solution is to identify test users in some explicit way and define a DeleteTestUser public API that is documented to only delete test users, but does so completely.