First of all, yes, this would be feasible. Your agency doesn't need to tap the phones, since there are no phones. The main task of your agency is to detect (and maybe even prevent) rebellions. Rebellions would be made by people. The agency would have their own people there, simple as that.
You could inspect the mail, but I don't expect conspiracies to be organised by post. At least not at the stages you would wish to stop it. If there are multiple rebel groups on several provinces, preparing an uprising that needs to be synchronized, then maybe. Although I would expect them to use actual messengers rather than trusting the Imperial Post for such important details.
If a group of peasants were trying to unite to rebel against the governor, they would have some agent ready to join their group and release their plans. Or someone in the group would be easily tempted to out them at the local delegation of the agency (it is well-known that they will pay well the information and give you their forgiveness for your participation, when people start having doubts about their chances, they will flee to tell you!), or someone you can extort, from other information your agency could divulge about them (real or fabricated) to threats to their children, their job...
They have no legal authority to arrest people, detain them, kill them...etc
Note they will have to face the consequences if caught, but they might do it. Or threat to do so to certain subjects. A group of assassins coming from another province (although in the same Agency district), doing their deeds and leaving.
None stays in one place for too long nor do they just choose where to serve.
This may work well for big cities. On rural areas everyone would know who the local spy is, the guy who arrived three years ago (and will leave in two years, having stayed for exactly 5 years, just like the guy before. Moving everyone at once would be useful for periodically organizing your assets, no so much for secrecy)
The entire organization is from time to time investigated, in secret or not, by the IG. The IG is a massive organization of fanatically loyal men and women who are above the law.
Quis custodiet ipsos custodes? You might have to develop on why these are fanatically loyal in your story so that they can be above the law. Are they brainwashed on a special school? Part of a cult? The emperor is similar to The Mule? They made an unbreakable vow?
And why can't the same be done for every member of the Agency?
they constantly have to justify the expenses
This may be a red herring depending on how far you go, I think. All intelligence agencies need some funds they can dispose of discreetly. You need some oversight of the expenses (in order to avoid corruption) but at the same time, that should not restrict its ability to use them. I expect their books will be full of things like bribery and payments to informants. How much can they pay them, or the value of the information.
In fact, the main problem they will face (as with any intelligence agency) will be to discern (at some point of the chain) the information posing real threats from those which are fake or irrelevant. A group of people badmouthed the emperor at a tavern, and your agency discovered it. Was it a conspiracy or a group of drunkards? Is it worth devolving the resources to spy each of them for... days / weeks / months? If someone is a bit short of money, what would stop him -as a loyal citizen of His Emperor- from uncovering a "conspiracy" he overheard to the rich intelligence agency? Even if it was made up? How to avoid that the agents infiltrated into the rebellious groups actually made them last longer (get paid for disclosing the attacks you are organizing "in order to conceal that you are an imperial agent", seems beneficial to them)?