To add to the above answer by DVK (since it is too long for a comment), owl posts were suspected to be intercepted only after "The Parting of the Ways", when the Ministry under Fudge started a smear campaign against Dumbledore and his supporters. And by that time, Dumbledore had revived the Order of the Phoenix and Kingsley, who was in charge of Sirius' case, had been alerted to his side, which was why he and Tonks were seen covertly misinforming the Ministry on Sirius' whereabouts: Arthur Weasley says in the Order of the Phoenix : "We've managed to convince a couple of people, though. Tonks here, for one — she's too young to have been in the Order of the Phoenix last time, and having Aurors on our side is a huge advantage — Kingsley Shacklebolt's been a real asset, too; he's in charge of the hunt for Sirius, so he's been feeding the Ministry information that Sirius is in Tibet."
During the previous two years when Sirius was on the run, nobody in the Ministry had any reason to suspect that he had any correspondent in Hogwarts or elsewhere, and least of all, Harry and Dumbledore. His presumed master, Voldemort was not on the scene, and his other family members are in Azkaban, while all other former Death Eaters like Malfoy had "converted", in the eyes of the ministry.
Thus, if wizards can make themselves untraceable allowing for exceptions, the Ministry could not have traced Sirius using owls, and interjecting the allowed exceptions did not happen for the reasons given above.