First of all, I think you should look for solutions already implemented by other people. For example, what do other people do in your case to prevent espionage?
A possible solution would be to have an "app" in the middle, which analyzes the information being sent, alters it and sends it to the same server and leads to which the spyware is trying to connect.
I read a little about the app's functionality and the information it collects is and I quote from the Wikipedia source you provided:
sent in clear
So, by running some tests and analyzing the way the information is collected, you can, if you have root access to your Android phone, redirect the spyware app traffic to a running process against the background of the Android operating system. This process would change the data that will be sent to the server to which the spyware is trying to connect. In this way, you can send data that matches another mobile phone (perhaps, literally falsifying data is a bad idea, because it can trigger alarms)
You should also consider any kind of validation processes that the spyware has implemented so as not to alter them.
Of course this is theoretical, but it is a realistic thing to do. Also, you'll probably need to know about Android programming (mainly in C or Java) and I.T.
This approach is invisible and does not require the uninstallation of the spyware app.