*haha* That one is actually pretty funny. You literally did shoot yourself in the foot.
Have a look at the source-code link-template.php line 1922 says:
if ( ! empty( $path ) && is_string( $path ) && strpos( $path, '..' ) === false )
The last condition strpos( $path, '..' ) is actually matched by the .'etc... etc...' in your example. The $path param in home_url() is checked for containing any .. to prevent directory traversal attacks. The $path param is only added to the url if it’s not containing any '..'. Just remove this and you’ll be one step further.
The next step is that any url containing /search/anything-else is treated as a search-results page in wordpress. The default pattern is search/(.+)/?$ You can see this through installing the Rewrite analyzer plugin and just filter for the string search/anything-else.
So you will need to make sure that the url /search/Used/MT/Billings/ is actually triggering your search logic here instead of the wordpress search. Otherwise your search url in the form of /search/test/test/test4/?s=asdasd&z=test&r=test would actually create a redirect loop, cause you use the permalink version /search/term together with the $_GET param version ?s=term.
This is not really a part of your question but just that you consider: Even if the redirect is working correctly in the first part, wordpress might decide to reformat the URL at the pageload following the redirect, cause it doesn’t recognize your search url structure, that is why you will need to make sure that your logic is executed on all that urls before wordpress does so.
For example you could add an own rewrite rule using add_rewrite_rule(), or hook to the parse_request action (which is a good action to handle custom url params in my opinion). Of course you could also handle this external (before wordpress) through adding some custom stuff to the .htacces or even through adding a directory structure /search/Used/MT/Billings/index.php (that may be the easiest way, but I wouldn’t recommend that cause that might get overridden by performaning a wordpress update later).
Edit
According to your newest comment, I really belief you may be better of using some rewrite rules, which take effect before wordpress, instead of messing around with WordPress core/Relevanssi. I wouldn’t use it in a plugin, but it will maybe fit just right for a custom development.
RewriteEngine On
RewriteRule ^search/(.*)/(.*)/(.*)/page/([1-9]) /page/$4/?status=$1&st=$2&ci=$3 [QSA]
RewriteRule ^search/(.*)/(.*)/(.*)/ /?status=$1&st=$2&ci=$3 [QSA]
That rule will internally rewrite this URL:
/search/Used/MT/Billings/?s=BMW&z=59105&r=150&m=150000&pmin=1000&pmax=30000&submit=Refine
To this URL (which is in my understanding the form Relevanssi will need it):
?status=Used&st=MT&ci=Billings&s=BMW&z=59105&r=150&m=150000&pmin=1000&pmax=30000&submit=Refine
You may want to replace the (.*) with some more specific regular expressions, regarding the possible contents of your query vars.