Why not send letters through the Floo Network?
Below are all possibilities, as there is no concrete answer I can find in the books or in Canon.
Say someone else happens to be walking by the fireplace, and they feel a letter hit their foot. They will pick up the letter and examine it to find "Grimmauld Place" on it. Harry will tell them the letter is for him and the person will either give / not give it to him and forget / not forget the letter and the address.
In this first scenario, it will depend on the niceness of the person and their ability to remember things. Also, if the person gossips, Harry will be in trouble.
The letter may be intercepted. Although Sirius's head was not, it is less suspicious to have a head going through the Floo Network than a letter. Heads go around all the time, and letters are a little less frequent. And if the letters are to Gryffindor and going to or from some random place the Ministry's never heard of, they'll be suspicious.
This scenario will depend on the attentiveness of the Ministry worker and how much they are watching the Gryffindor fireplace. Fudge will have put someone loyal to him in this job, undoubtedly.
The letter burns.
No one knows if this will happen. After all, wizards are magic and letters are not. It would be simple to add a non-flammable charm to the letter, though.
The letter goes out of the wrong fireplace.
There are also quite a few places this letter can go! Floo powder can misinterpret the speaker's words (as seen in Harry's second year at Hogwarts). It would be less worrisome if it was the Ravenclaw, Hufflepuff, or Headmaster's fireplace. But the Slytherin fireplace would be devastating.
The letter needs a body part to go with it.
The toast went with Mr. Diggory's head. We don't know if the toast needs the head to go through. So Sirius may have to stick his hand through with the letter and cause a lot of screaming and alarm.
Fireplaces don't like letters.
Fireplaces may have tempers. It is the magic world after all. Either that or fireplaces in the Floo Network are enchanted to not allow letters through.
Owls are better.
They're magical pets. I'm not saying fireplaces are bad pets, it's just owls are extra special in the wizarding world. Many wizards prefer owls. Hedwig would also be mad if Harry chose a fireplace over her.
If Floo network, then not owls.
Continuing from the "Owls are better". If the Floo Network were for mail, magic owls wouldn't exist as pets. Wizards would use the Floo Network as new technology and let them roam wild. Only a few would use the owls because owls take longer to go there and back.
Most of this is speculation, but through deep thinking and thought it is possible to realize all these scenarios are possible to some point. The main focus must be put on Fudge though. Below is the point that I consider to be the deciding factor.
Umbridge was able to find Sirius by watching Harry's mail. If Harry's mail was sent through the Floo Network (controlled by the Ministry), it would end in the same result with possibly more disastrous consequences. Somehow, despite the secrecy behind Sirius's first meeting with Harry, Umbridge figured out that he was using the Floo Network. Continuing to use the Floo Network will allow the Ministry to read all of Harry's letters without him knowing, perhaps for the entire year. The Ministry might even be able to use the information gathered to capture Sirius, despite the Fidelius Charm, which can be broken.
Therefore, neither Harry nor Sirius sent letters through the Floo Network.