There is a solution to both of these issues, one of which has already been raised by one poster: Having separate, non-work related PCs. These can be kept clean (just run the browsing session under VMWare and wipe it every time someone logs off). No need to worry about viruses or other nastyware. Or even data hygeine - it's all wiped from session to session, so anything that does get on to it won't stay for very long.
Having separate PCs on a different subnet, using different firewall rules (all other machines you can just block from using the internet, period) - means it's easy to also throttle bandwidth. Not that bandwidth should be too much of a problem - if people have to visit a specific PC, they can't pretend to be working (as also said, earlier). If you also only have one internet PC per say, 100 employees, you've already managed to implement a 100:1 contention ratio, with no special configuration needed. :)
By the same token, providing a payphone on the company premises also sends the message that you understand that people may have to make personal calls from time to time, but that they should pay for them. You can easily configure phones to call extension numbers only (except for certain types like sales, account management, etc). The rest can use the payphones for external calls (although incoming calls, e.g. family emergencies, will reach them at their desk). Not everyone can use mobile phones effectively, by the way: I personally work two levels underground, where of course there is no mobile phone signal.
As for wages being appearance money, no I don't think so. I think it's a little more than that (something along the lines of "I pretend to work. They pretend to pay me.") ;-) Seriously though, I take my work seriously - and I would support having internet access away from the desk - in an open-plan office, so you can see exactly who is using the internet machine, and when. But I would support having such a machine, in case an employee needs to arrange something personal during work hours.
To those who say work stuff is for during work time (with absolutely no exceptions), you must live very slow and relaxed lives. You must also think that any employee must be treated like a robot, for they cannot be allowed to have worries or separate lives. (Try having a serious unresolved argument with your wife/lover/girlfriend and then try concentrating on work. Just try it, and you'll see how hard it is to *really* separate work from personal stuff).
For the rest of us, who do not live in the same world as you, we often need to get things done quickly, solve personal and/or family problems - and during work hours. It doesn't mean that people should spend all day surfing the net, or yakking on the telephone: Ordinarily, they should be doing the job they are paid to do. But it does involve an understanding that not all employees' on site needs will be business-related. Good employers recognise this, while also limiting the potential losses caused by abuse of internet and phone facilities.