That should be possible by using 2 views, as one View will respond to the query (by taxonomy) and hence exclude all posts, not within that taxonomy.
The second View will then respond to the second query (all posts not in a certain taxonomy)
Hence, you can set up 2 Views.
The first has a query to return posts in a term XY, and complete the Loop.
Then the second View will have a Query that returns all posts NOT in the term XY, and also here complete the loop.
Then, either insert the second view just below the [wpv-layout-meta-html] in the first View's Output Editor, and that first View to a page, or both Views below each other in a page.
To solve the "2 different blocks" issue, you could check the box "Disable the wrapping DIV around the View" in each of the views, which will ensure no additional HTML is wrapped around your loops, hence, you'll not end up with too many Divs in a page.
About sorting, you would still have the issue that a View, just as the WordPress query, will always listen to what you set in it, so if you exclude posts that are not in a term, or include posts in a term, it will and can only listen to that.
So you will need to have either 2 Views or no query in the view.
You could for example order by terms. This means, create a Taxonomy View, order by Terms, and then list the posts in that view.
This would ensure that posts with term A come before Term B, but you still could not show posts without any term at all.
(since those would be excluded from the query by the ordering)
Related to search, you should be able to add search handles manually (means, you need to populate a custom link or select that once clicked, updates the URL with a URL parameter)
If then you set both views to listen to the same URL parameter, both will get updated on search.
But this cannot work with View's inbuilt search, as it adds Views-ID's so to make sure, only the view searched will be updated
