I thought it was perfectly legal to look thru a suspect's trash, as long as no trespass is required to gain access to it.
I seem to recall a dispute a while back between Microsoft and Oracle in which Oracle allegedly decided to look in the trash of an organization that was lobbying for Microsoft. Oracle's rentacops supposedly rented space in the same office building, so that they would not need to commit a trespass in order to get at the dumpster.
Disclaimer: I am not a lawyer.
I believe the trash bins being searched through were on private (apartment house) property. They also would have contained the garbage of many people who were not suspects. While a warrantless search might have stood up in court, as you suggest, the authorities might have figured that it would be safer to get a search warrant.