There are even little cheap hardware things, that you can put between your modem and your line. They'll let you only dial the numbers you let them to (i.e. you ISPs). Or block all premiums lines efficiently.
Antivirus-Software will most probably don't find anything, as it's technically not a "virus" or "worm" or "trojan". Also this is some normal kind of software, and I think antivirus-people are legally not allowed to delete other peoples software (like a virusscanner couldn't uninstall Microsoft Office for you).
Spybot Search & Destroy, AdAware, Bazooka Scanner (or how was it called?) do a good job, a long with up2date
virus scanners and firewalls. Don't forget Windows Updates, and get some knowledge about computers and how modems work.
In you case, I'd keep that phone bill of course and only send away copies of it, obviously. You might as well wanna try to get some EVIDENCE from your PC, i.e. that it was infected. But probably too late now, as the ad-scanners will have deletes lots of proof. Also it's not sure what it could help you.
It could help if you team up with other damaged people, very often they group together on forums and have one "collect suit" or something.
For your PC, I can only recommend re-formatting. Otherwise you won't get it REALLY clean. Unless you know all the special places where software can hide and start itself in Windows.
My old modem used to make a loud CLICK-sound whenevcer it dialed. Plus it had a speaker built in. So I could always tell when it started to connect. So now hidden dialing for me.
Also I strictly turned it off when not using the internet.
Always become suspicious!