Think you answered it yourself ;-)...
"I always assumed that he must have gotten blasted by a storm trooper or something"
In answer to...
"Why would the storm trooper blast 3PO and just leave his bits lying around? Wouldn't that raise suspicions?"
He doesn't, they throw Threepio into the trash where nobody should find him.
A more pertinent question would be: How did Chewie possibly find Threepio in the trash, in a vast place like Bespin???