There are a number of techniques for dealing with the problem of external apis. I'm going to try to describe several possible approaches that may be helpful.
This is where your tests assert that a particular sequence of calls was executed. This is the technique that you've tried, and you discovered where it falls down. It works really well when the external api is very simple. However, for complex apis it typically becomes problematic. The tests are brittle and don't even do a good job of catching real problems.
You can help brittleness of these tests a bit, by relaxing your tests. You typically don't need to assert the exact sequence of function calls produced by a test. Perhaps your tests can allow more lee-way.
The ideal solution, in many cases, is to actually test against the real implementation of the api. That way you can assert that what you want to happen is actually happening and not worry about the exact parameters you passed to the API. As you note, "I can't configure the external system from my tests, so integration tests are out of the question." So this looks like it may not work for you.
But depending on why exactly you can't configure the external system in a test, there may still be a way to use it. One possibility is to setup your tests such that they can be run in two modes. In the first mode, they actually run against the external system, and verify that the correct things happens. However, they also record the sequence of api calls that were made. In the second, you simply verify that the same sequence of calls were made.
During normal development, you simply run tests in the second mode, on the assumption that you don't usually need to modify the calls that were made. But in the case that you refactor the code and change the calls, you re-run the tests against the external api and recapture the sequence of calls made. Then you can continue coding having your tests maintain the new sequence.
Recording the Sequence
Another possibility, is to have two modes again. In recording mode, you record the sequence of calls made to the external api. In verifying mode, you verify that you are still making the same calls. Normally, you use verifying mode. However, whenever you do need to change the sequence of calls, you rerun the tests in recording mode to capture the new sequence of calls. You can then look at the diffs between the old and new sequence to verify that the sequence still makes sense.
Use a Fake
Instead of a mock, you can implement a fake. The difference is that the fake acts like the external api. It models the external api, maintains similar internal state and/or produces the same results. Instead of verifying that the right calls are made, verify that the fake got put into the right state or provided the same result. It can verify any number of rules about what the callers of the api are allowed to do. For example, if you can't call the "foobar" method before calling the "baz" method, then the fake can throw an exception.
Fakes are very nice and flexible, but do require time to implement.
Sometimes you may be able to improvise a fake by building on existing libraries/solutions. For example, a "real" SQL database can be faked by using an embedded database, such as H2.
Avoid The Api
You can try to structure your program so that as little as possible actually has to interact with the external api. This may require some clever thinking. Typically, you can reduce the amount of program that directly interacts with the problematic api to a small part.