Optimal knot placement, though seemingly simple, can be a gnarly problem due to degeneracy in many cases. Anecdotally I've found quadratic splines to still be somewhat tractable with exact methods, but polynomial splines with cubic or higher orders can be tricky, especially when they are large-scale.
For derivative-free optimization, you can sometimes get speedups from just adopting a embarassingly parallel algorithm like Particle Swarm. These types of stochastic algorithms aren't necessarily algorithmically better than Nelder-Mead Simplex, but they can explore a larger terrain in parallel, which may help. If you can find some parallel stochastic code, you should be able to spin up a VM on the cloud with lots of cores to help you search the space.
I've had good results from simplex; i'm a bit sad to hear there isn't some magical algorithm that will give me a massive speedup over it.
I haven't tried automatic differentiation. That seems extremely daunting given the volume of code in my problem. Someone has done some groundwork on AD of the main library i use in my model, but it would still be a serious bit of work.