Q:

If I suspect my server is compromised then should I disconnect it immediately or not? From Power or Network?

According to Mandiant, you should not:

Mistake #1:  Immediately entering “remediaton mode” – also known as playing “Whack-A-Mole”
  ... as described here:  http://blog.mandiant.com/archives/1525

Are there scenarios when it's prudent to take immediate action by disconnecting? 
Merged with this question as the answers should be useful and similar:
When a server gets rooted (e.g. a situation like this), one of the first things that you may decide to do is containment. Some security specialists advise not to enter remediation immediately and to keep the server online until forensics are completed. Those advises are usually for APT. It's different if you have occasional Script kiddie breaches, so you may decide to remediate (fix things) early. One of the steps in remediation is containment of the server. Quoting from Robert Moir's Answer - "disconnect the victim from its muggers".
A server can be contained by pulling the network cable or the power cable.
Which method is better?
Taking into consideration the need for:

Protecting victims from further damage
Executing successful forensics
(Possibly) Protecting valuable data on the server

Edit: 5 assumptions
Assuming:

You detected early: 24 hours.
You want to recover early: 3 days of 1 systems admin on the job (forensics and recovery).
The server is not a Virtual Machine or a Container able to take a snapshot capturing the contents of the servers memory.
You decide not to attempt prosecuting.
You suspect that the attacker may be using some form of software (possibly sophisticated) and this software is still running on the server.

A:

The answer depends on your level of sophistication, the level of sophistication of the attacker, and your goals.
The Mandiant blog post, from one of the leading providers of incident response and computer forensics services, is intended for sophisticated organizations responding to an Advanced Persistent Threat (APT).  One of their concerns is that you might not actually even resolve the problem if you can't observe the attackers work across various systems on your network.
But most security incidents are less sophisticated attacks on poorly administered machines.  In this case I think you're better off following the advice in the highly rated answer to the Server Fault question "My server's been hacked EMERGENCY", which suggests that disconnecting the server is indeed typically the first response, though you should not act in haste.

A:

Similar to what @AviD said: if you can somehow determine that this compromised app/host/network is actively in progress with another attack, it might be wise to at least pull the network cable, right? This also assumes that you cannot control the attack in some other way, or that things have gotten extremely out of control.
This probably precludes any process or infrastructure, and also requires some very low skilled or unintellectual staff.
You know it's amateur hour when they pull the power, network, or disks on a compromised machine.

A:

Useful answer over here by Robert Moir - some very good chat on Serverfault on this.

