Indeed, the MP3 patents and a small number of similar ones are the only good examples of nontrivial software patents. They are, sadly, a tiny fraction of all software patents.
Regarding whether the MP3 patents were a good thing or not, that is as you say debatable. It made developing the technology profitable, but it also created barriers to interoperability - for example, it is problematic for open source operating systems to support MP3s, and they are forced to do various workarounds of dubious legality. Compare this to the situation on the Web: Anyone can write a web browser, without having to pay anyone else.
Well my first encounter with software patents was with the Diffie-Hellman and RSA patents. Followed promptly by the Lempel-Ziv compression patent and then the MP3 patent. Can't say that I enjoyed any of those encounters :-)