I know that the Corleone brass (in the novel) suspects Clemenza and Paulie, but I don't think that made it from book to screen. If one simply saw the movie, he or she might have no indication that the Corleones suspected Clemenza. Clemenza is present at the "council of war" with Mike, Sal, Tom and Santino who is pretty sure that Paulie "gave up" the "old man."

The only clue might be when Clemenza asks Santino if he wants some of Clemenza's men sent over and then Santino answers "no," but once Clemenza leaves he tells his wife that he is sending some men over (presumedly from his regime).