I've bumped maxRadius both client-side and server-side. maxRadius = 15000 However when I search for structures, I never find anything outside of a radius of 2000.

Searches stop when either the max radius is reached, or the max number of samples have been taken. Looks like your maxSamples value is set to 50000, and this sample threshold is being reached long before the radius threshold is reached. If you want to search further than 2000 blocks, you'll have to raise maxSamples as well.