Hi,
Well, this is a tough one, but I think you can do it via the filter templating system.
If I see correctly, you are using the custom field filters. For that, you will have to look for the wp-content/plugins/ajax-search-pro/includes/views/filters/custom_field/asp-cf-header.php file, and follow the instructions in the tutorial to make a copy of it.
Then you can try moving the legend tag, outside of the filter scope.
I may suggest using custom CSS to hide the legend tag instead, and printing it above the actual fieldset again, as a paragraph or a div element, so it does not break the actual original structure. Something like this: https://gist.github.com/anag0/5197f820cb15050fa5940989db9b2101