The registry keys are the big tip off that you have a virus. I also encountered the same keys during my check. These keys are changed as soon as the virus has infected your system. It is part of its process.
The fact that Rkill showed something was running is a huge indicator that you have malware. If Rkill kills something, it isn't supposed to be running there. Hence, virus, or malware. Generally, not good software.
It seems that the rule is if it does not work right, and can not find any virus problems, one is to assume that there is a viirus. and reformat the disk in a another machine. Then take your chances that it will happen again, because I don't know how are where it happend in the first place. This whole process seems not very productive. Isn't there a better way?
Please note: I am generalizing the following statements. This is what your IT guy thinks about all the time.
As an IT guy myself, I can offer the paradigm of "how much money do I want to spend fixing this problem?" I am bound to preserve as much data as possible. I am also bound to resolve problems in a timely manner for my employer as to not waste his money. One must strike a balance here to achieve this cost effective operation. This is where you get caught.
Productivity on both of our parts is at risk as well. The longer I leave your machine this way, the longer you complain about it and fail to achieve your tasks. The faster I can resolve your problem will result in you being able to get back to work faster.
You, as an employee are responsible for your data. My job is to make sure that you are setup with instructions on how to keep your data safe and redundant. I also keep the servers up and running as well as backed up with information you place on the server. I am not, however, responsible for careless actions resulting in data loss. This includes physical damage to the machine or malware activity. I can minimize this by restricting access to your Internet connection by restricting your machine's ability to get online without going through my server. But in the end, all that does is get you upset that you cannot go to XYZ.com to check out the latest sports scores.
There are many times where I would rather troubleshoot an issue than reformat because it genuinely interests me to find out why I see it. If I see a trend with a particular issue, I will isolate the machine and work on it to resolve the issue to keep it from happening again. However, realizing the balance between cost and efficiency, sometimes I have to say **** it and reformat your machine. It pains me just as much as it does you, for varying reasons. Some the same, some very, very different.
BTW: good on you for backing up. I wish my users paid more attention to their information.
Again, I do not wish to offend in anyway. This was mainly to explain the thinking of your IT group. In the end, with this situation, you could have had this resolved a month ago if you would have let them reformat the machine.