Почему JUnit 5 выполняет тесты в произвольном порядке?
В BeforeEach наполняешь базу перед каждым тестом.
По логике JUnit занимается модульным тестированием
Нет. На JUnit можно реализовать любой вид тестирования. Даже Acceptance и E2E
следовательно методы теста не должны зависеть друг от друга. 
Это хорошая практика для любых тестов.
Тогда возникает парадокс. Если в каком-то методе происходит удаление записи из БД, а в другом пойдет обращение к этой записи, которая уже была удалена, как быть?
Привожу пример. Один метод проводит проверку по поводу удаления записи из таблицы БД по id. Другой метод должен прочитать эту запись по id.
Для этого есть setup, teardown, AAA, и контроль параллельности (тесты, которые работают с общим окружением, не должны запускаться одновременно, а только последовательно)
Каждый тест должен сам для себя устанавливать предусловия и чистить общее окружение после прогона.