I just tested some of this on mine (v7.5.2, not even the most recent) and didn't have any trouble doing something at least very similar to what you're wanting. I typed your example "my" into the search box, and it comes up with a list of artists with "my" in their name, then a list of albums with "my" in the title, and finally a list of songs with "my" in the title. I can add any of them to the current playlist by clicking the plus next to them (or use the play icon to have it replace the playlist), or if I want to see more info on the artist or album I can click on it and then go back after looking / adding specific tracks, or just open it in a new tab. It only took a few seconds to do the search and display the results, and that's with it running on hardware roughly on par with your average netbook (I run it on my fileserver). The only slowness I get in the web interface is the initial loading, and it takes several seconds to display all the album artwork on the playlist (it seems like it's not caching it at all, instead pulling the embedded art from the individual files every single time).
As for reordering the queue, I don't see a way to move several files at once, but unless you have some long, complex playlist you're trying to create, it takes practically no time to just drag and drop the tracks to different spots in the playlist (there's zero delay from the server, they move as fast as you can move). Unfortunately, unless there's some logging or a plugin for it, I'm not aware of any way to view previously played tracks that aren't still on the playlist (random mix will only keep the 10 most recently played tracks on the playlist). I've never really encountered an issue of needing to do that myself, but it sounds like a dealbreaker for you.
To offer a counter-counter for the usefulness of the SB, I've found it absolutely great for organizing and sorting through my music collection (11,000+ tracks, with a lot of CDs still not ripped). I can browse my main collection the usual ways (artist, album, genre), or for classical music I can browse by composer, conductor, or symphony/performer, and then for soundtracks I can browse the same way as my main collection, or just pull up a list of the main series/game titles without having to know the artist(s) or sort through the whole list of everything (I added a custom tag to my FLAC files to include that info). So if I wanted to find all the music from any versions of "Ghost in the Shell", I can just go Custom Browse => Anime => Ghost in the Shell, and then have a list of all the soundtracks from both the movies or TV series. I pick the one I want, and then since I can sync multiple Squeezeboxes together, I can go from my PC down to my DIY cave and continue listening without interruption. Also, in my case, since it's not tied to any desktop PCs, if I need to reboot for an update or something, or I just don't have the computer turned on, it has no effect on the music.