Clearing static state before testing each method

how I can ensure a solid test design.

Well, like you said:

external static state (which generally should be avoided, I know)

But, if you're determined/doomed to work with a bad design here's some things I've learned the hard way.

// works but a bit questionable
    @BeforeEach
    void setUp() {
        Cache.clear();
    }

is a bad idea. Doing the clear before is fine. Just not each. This one size fits all approach will seem to work fine right up until it doesn't.

A better solution is to put the clear call at the start of each test that needs that particular form of clear. This way you're making the tests needs obvious. To make this work well, don't fix things the test doesn't care about. Doing that makes what the test cares about clear.

Some argue that you should put the clear after the test to clean up nicely for the next test. I argue against that for the same reason. The test should know it's own needs better than anything else. Also, when done "before" style, a failure to clear makes the test that needs fixing fail. Not some other one.

Yes I know this is more work. This isn't the easy way. Just better.

How do I make sure my tests do not depend on their order of execution?

The usual answer is to design your test subjects so that they can be configured to be isolated.

Michael Feathers (Working Effectively with Legacy Code) refers to this sort of configuration as a "seam" -- the idea being that we can vary the way your test subject works by changing code somewhere else (ex: in the test).

My SUT class depends on external static state (which generally should be avoided, I know).

So what we would normally do is to introduce a seam such that the dependency on shared state can be controlled from the test.

(In effect, what we are doing is making "... and it needs to be possible to isolate the SUT..." part of the requirements -- it's a design constraint.)

I'm not 100% comfortable introducing changes in business code solely for testing

Yup - I get it. The "advanced" answer is "get over it". The basic idea is analogous to working in hardware - being able to connect to the test pins to communicate more directly with the device is necessary to verifying that it does the right thing, so that gets built into the design.

The Doctrine of Useful Objects covers a lot of these ideas (with a bias toward the idea that any object that is complicated enough to need it's logic tested should default to being isolated; you need to "opt-in" if you want to connect the logic to something on the outside).

I am a little confused, because you already seem to do what I will suggest, but I will spell it out anyway:

You inject your cache just like your data access. Your third party does not support that? Well, then wrap it.

Create a ICache interface with the methods you need (get/put).

Inject this interface everywhere you need a cache, just like you inject your data access everywhere you need it.

Implement one class for ICache that is the actual cache third party library. Implement one class for ICache that you can use for unit testing and that is some kind of memory cache.

Unit test the actual implementation. For all other tests using an ICache, use your non-static, in-memory implmentatation.

I am not a big fan of mocking frameworks. If you are into that, you can obviously use your mocking framework to setup up a mock, instead of writing a memory cache.

So your unit tests become (sorry if there is a minor syntax error, I'm not a Java programmer):

/* This is the essence of it:
   MyClass is one of Cache's clients: if it can get 
   a cached MyData instance, it doesn't use its dao */
@Test
void doSomething_ifDataCached_noDbCalls() {
    MyData data = new MyData("some expensive data");
    ICache cache = new UnitTestInMemoryCache();
    cache.put(data);

    MyDao dao = mock();
    MyClass myClass = new MyClass(cache, daoMock);

    myClass.doSomething();

    then(daoMock).shouldHaveNoInteractions();
}

@Test
void doSomething_ifDataNotCached_noDbCalls() {
    MyData data = new MyData("some expensive data");
    ICache cache = new UnitTestInMemoryCache();
    // no cache.put(data); call this time
    MyDao dao = mock();

    given(dao.findData()).willReturn(Arrays.asList(data));
    MyClass myClass = new MyClass(daoMock);

    myClass.doSomething();

    then(daoMock).should().findData();
}