to be safe I would also run the spyware and AV programs while in safe mode, just to be sure.
Also you can delete the entries from your firewall and see if they try to access the firewall again, you should get a pop up of some sort asking about a program wanting access through the firewall. this may help determine if it is legitimate.