The film never really shows us that Paulie did betray the family (I've never seen the deleted scenes. Do they go further in implicating Paulie?). My guess is that the Corleones are not big believers in coincidences. Besides, if Paulie had been in on it, and was on duty, he would have remained suspect if he hadn't taken a bullet himself, or at least taken out one of the hit-men.