This question is essentially asked in the books themselves, though about a different character. In the beginning of Half-Blood Prince we find the following conversation between Slughorn and Harry:
“All ex-students, all signed. You’ll notice Barnabas Cuffe, editor of
the Daily Prophet, he’s always interested to hear my take on the
day’s news. And Ambrosius Flume, of Honeydukes — a hamper every
birthday, and all because I was able to give him an introduction to
Ciceron Harkiss, who gave him his first job! And at the back — you’ll
see her if you just crane your neck — that’s Gwenog Jones, who of
course captains the Holyhead Harpies. ... People are always
astonished to hear I’m on first-name terms with the Harpies, and free
tickets whenever I want them!”
This thought seemed to cheer him up enormously.
“And all these people know where to find you, to send you stuff?”
asked Harry, who could not help wondering why the Death Eaters had
not yet tracked down Slughorn if hampers of sweets, Quidditch
tickets, and visitors craving his advice and opinions could find him.
The smile slid from Slughorn ’s face as quickly as the blood from his
walls.
“Of course not,” he said, looking down at Harry. “I have been out of
touch with everybody for a year.”
Here Harry is asking why Slughorn couldn't be tracked if people are sending him all sorts of stuff all the time. Slughorn's answer is that people have not been sending him stuff. This response shows that if people had indeed been sending him stuff then others would have been able to track him (i.e. owls can be followed).
This response also indicates that there must be something one can do to prevent owls from finding him. Slughorn was able to ensure that none of his students nor any Death Eaters would be able to send him things. We don't know what this prevention method is (a spell, or something else) but it apparently works (although Dumbledore managed to find him, but hey he's Dumbledore.)
Finally, this also shows that the method of prevention is either all or nothing. If Slughorn was able to only prevent certain people from tracking him (like Death Eaters) he surely would have allowed his former students to continue sending him gifts.
Another potential indication that owls can be tracked comes from Goblet of Fire:
Harry pulled off Sirius’s reply and offered Hedwig his bacon rinds,
which she ate gratefully. Then, checking that Fred and George were
safely immersed in further discussions about the Tri-wizard
Tournament, Harry read out Sirius’s letter in a whisper to Ron and
Hermione.
Nice try, Harry.
I’m back in the country and well hidden. I want you to keep me posted
on everything that’s going on at Hogwarts. Don’t use Hedwig, keep
changing owls, and don’t worry about me, just watch out for yourself.
Don’t forget what I said about your scar.
Sirius
“Why d’you have to keep changing owls?” Ron asked in a low voice.
“Hedwig’ll attract too much attention,” said Hermione at once. “She
stands out. A snowy owl that keeps returning to wherever he’s hiding
... I mean, they’re not native birds, are they?”
So, given that owls can be used to track, and given that wizards can do something to prevent this, the question should now be phrased as:
If Sirius wasn't blocking owl tracking then why couldn't the Ministry easily find him? And if he was blocking owl tracking then how was Harry able to correspond with him?
The answer may be very simple. It is possible that when Sirius first escaped from Azkaban he did engage the prevention techniques, thus allowing no one to find him or correspond with him. At that point there wasn't anyone that Sirius wanted to correspond with, so it wouldn't be a big deal for him to "go dark". This would have prevented the Ministry from tracking him at that point. By the time he met Harry it was almost a year later. By then he might have removed the tracking-prevention so Harry could contact him, but the Ministry had already given up on using owls to try to track him.
A slight variation of this idea would be that the Ministry never even bothered trying in the first place (regardless of whether Sirius had actually engaged the prevention mechanism) because they knew how simple it is for a wizard to block owl tracking.
