If this is the case, is the test really testing something useful? Tests should verify that the code works as it's intended to work. If pre-existing (but presumably valid) data can break the test, then surely there's states where whatever behaviour is being tested won't work in production?
Provided the test is creating and verifying its own data, it's not really non-deterministic except in a very technical sense.
Imagine I'm testing a web page that shows a list of all customers who have placed at least one order.
If I set up the test by wiping the database and adding ten customers, I can assert that the list of customers should contain those ten and no others, giving it ten rows.
If I don't wipe the database, the web page may show more than ten customers - and I can't tell if the extra entries indicate a fault in my code or not.
After all, the code doesn't show the 10 most recent customers that purchased an item, it shows ALL customers. You could hide a pagination bug where only the first page of results functions if you wipe the database first.
Then your test code needs to take into account the current state of the database when creating input data for the code under test. It is more complicated than with a know start state where you can pick fixed data, sure, but it's doable.
... and you're on your way to writing an application, not a test!
Tests should be as simple as possible, and a clean slate goes a long way toward that.
A test should be riddled with as few "needs to do" responsibilities as possible while still achieving the intended coverage.
In both case, i need to control my testing environment.
Randomizing inputs could be used in a third scenario for extensive testing, a bit like fuzzing. But it's yet another different usage.