There's a new case out there called "Bilski v. Doll" (http://www.uspto.gov/main/homepagenews/2009jun26.htm) that concerns business method patents. While not exactly on point, it may concern software in the sense that software is not (usually) making a tangible "thing".
Also, designs can be protected as either a copyright or by a design patent. Further, ideas CAN be patented with a utility patent in the sense that you don't need an actual working version of what you want to patent.
Moreover, Microsoft could sue the developers of OpenOffice for creating software that mimics Microsoft's if it was the same as Microsoft's (or even just very similar under something called the Doctrine of Equivalents).
As for the "tried and true practice" of not checking - I've found that to be untrue. Many companies get what are called "freedom to operate" opinions which are written by lawyers. A simple way of thinking of these are that they are something written by an attorney saying that a patent search has been done, and X amount of relevant patents have been found. However, the client's product does not infringe any of these patents for the following reasons (which are then discussed in some detail). You can also get an opinion concerning a specific patent, if you are aware of the existence of one. These noninfringement/invalidity/unenforceability patents state that the known patent is not infringed by the client's product and/or the patent is invalid and/or the patent is unenforceable.
The triple ("treble") damages thing is for willful patent infringement. Having an opinion is meant to nullify this. True, it can't be willful if you haven't done a search and are not aware of what's out there, but I wouldn't necessarily want to take that risk. Just my opinion.