Can you totally ban a PC from the local network?
Solution 1:
It's true that clients can alter their mac addresses, thus rendering any sort of filtering on that more or less useless.
On wired LANs, with the right sort of switches, you can control with MACs are allowed to connect from which ports, and limit the number of MACs that are allowed on a port. This can help, if the clients are always attached and turned on, but someone with the knowledge of what the MAC is on a particular machine could unplug the legit box and change their MAC address to match. Some switches can be configured to block a port if the link goes down, and require administrative intervention, but that doesn't scale well at all.
So, this is exactly the sort of thing that the 802.1x protocol was intended to help with. In brief, it requires that a client present credentials that are authenticated before network access is granted. The wikipedia article on it has a good description of how it works.
As far as I know, without some sort of access credentials, what you're trying to accomplish can't be done. 802.1x at least puts the authentication at the network level, rather than allowing access, and then blocking use of network resources by some other means.
Solution 2:
You are looking for something called Network Access Control. There are all sorts of ways to implement NAC from various vendors. Additionaly in a windows only/mostly environment you can implement domain and server isolation (not that you can't accomplish a similar thing in a *nix environment but it's almost more pain than it's worth). With domain and server isolation while you aren't preventing any access to the network per se, you are preventing access to any of the servers and workstations on it, and if it's a machine you own you can control what servers and workstations that particular server/workstation can talk to.
Solution 3:
If physical access to a network (via hardwire or airwaves) is achievable then always assume that the machine can participate at the transport level. What it can do beyond that is what you really should be concerned with and where you should be focusing security efforts.
Solution 4:
Depending on the size of your network and type of layer 2 hardware you have, you can permit only the mac addresses that you want.
Solution 5:
How is the PC connecting? wireless? wired? Is that a PC someone brings to work like an employee using his own laptop. In this case you may take legal or internal security measures (mainly if the employee changes his MAC address to connect and hack a whitelist MAC address restriction).
If it's an outside person invading the network like a neighboor using your wifi, I think the best is to never let a wifi connection non password protected and encrypted.
If it is a VPN access... if you use a vpn with certificates like openvpn and if he has one you can ban it using the crl option.
The solutions can be different for each case and not only network or server related.
Now, if it's your CEO using his own laptop full of viruses... good luck ;) but you can offer to clean the thing maybe :)