Or just use GET since it already works. I don't see any problems with large query params. You can also split the search into a POST request and a GET request for the result.
Overall, I'm not necessarily inherently against new HTTP methods. If equipment that is supposed to be transparent to HTTP isn't, should be solved elsewhere, not by a new HTTP method.
It's better to fail on the ones that slip through the cracks than to leak data. And the failure alerts people that updates are needed here.
Most servers will reject URLs after a certain size, 4-8KB.