I have a legitimate and legal software program that allows users to
attach large files (i.e. digital pictures, powerpoint files, etc.) to
their emails.  The program is free.  The problem is that the software
is being removed by Anti-Spy programs (i.e. AdAware, Spybot search and
Destroy, Yahoo Anti-Spy, etc.)--(I also have written and requested to
be removed from their lists of spyware companies but they are not too
responsive to do so).  In addition, the software is being ripped
out/removed by my competitors who are present on the same users
computer.  Originally I implemented a process of requiring a 'kaptia'
box when a user accesses the add/remove programs and wants to
un-install my software; however, my competitors and the Anti-Spy
programs are still somehow removing my software.
My software is free to users and is not ad supported (which my
competitors show tons of pop up ads to users in order to monetize
their 'free' product).  I want to keep my software free and at the
same time allow my users to remove my software if they legitimately
wish to do so but I want to prevent the Anti-Spy companies and competitors from
illegally deleting my software from a users desktop.

What measures can I put in place to prevent this from happening?

Anti spyware software will only remove software that is spyware. So
your software must fall with in those guidelines. Which means it
returns information back to you. There is nothing you can do to stop
this really. Even the most advanced trojins are stopped by a
collection of secutriy apps on the market. No matter what you try make
sure that you are follwing the rules or you could end up in a lot of
litigation.

http://www.ftc.gov/
The Spy Act includes 21 pages of dense regulations that specify what
software can and can't do and under what circumstances it must seek
explicit permission from the user to proceed.

Change the name of your software.