I installed Lbuntu on an older ultra-portable machine, and while not extremely pretty the UI is extremely snappy -- and mostly resembles win 95. I do miss the ability to search for a program by name, but that is about it.
Lubuntu is using LXQT these days right? I'm running it on arch, but by default that DE should support menu searching out of the box, and if it doesn't I expect it's been configured out for some reason. Definitely worth playing around to bring it back.