Actually, to be really serious here for a sec, I think your original plan is fine. Leave a note, even. But don't take it out of the bag, don't punch holes in the bag, and don't, for the love of god, throw it. The original plain is not only evil fun, but if you get caught, the worst they can likely do to you is make your life miserable in return. The other plan they might be able to press charges for harassment . . . or worse. With the original, I think they'd be laughed out of court. I mean, their dog, their poop, neatly in a sealed baggy? YEah, no problem. Loose dog poop on their porch or thrown at their house . . . um . . . yeah, you might lose that one.
Required disclaimer: This is my personal and not professional opinion!