How to find a model number that replaced an old Shimano part
I hate to say this, but You're going to have to make a trip to your local bike shop. Chances are, if they're in the US, and they carry Shimano parts, they buy from Quality Bicycle Products (QBP). The company has an online catalog which you can search part numbers both active ant inactive, as well as related models. This catalog is only accessible to bicycle shops, and not the general public (though feel free to open your own shop, we only need more of them :-) ).

They'll be more than happy to assist you there, and hopefully find you an answer.

Now, buyer beware that this is only a guess, but based upon the internal levering mechanism that you describe, the BR-M580 looks to be the successor in the LX parts line. I see the same mechanical features, but from an upgraded parts standpoint. Like I said, only the parts shop will know for sure.

Now onto the actual question; the process. The shimano parts website holds a database of some of their part numbers. I simply searched your part number preceeder, the series, and the line (eg "BR-M DEORE LX") and I sifted through the disk brakes, and found similar pad brakes in a higher line.