Is it possible for an intruder to restart a Linux server remotely (without having internal access)?

Generally speaking, yes: if you have a flaw that leads to remote code execution with root access, you can do it.

As a matter of fact, it's possible for a specific flaw not to lead to a remote code execution but still lead to a kernel panic and server reboot.

Given the way you've phrased your question, however, I doubt you have the necessary knowledge to perform a postmortem on a system a detect this kind of attack: I would suggest you hire a security professional if you really want the system examined.

You need root access to restart a Linux server. If your root account was compromised and you have ssh enabled, then it's entirely possible for someone to remotely reboot your server. Judging by the quality of this question, I strongly recommend that you hire a consultant with the revelation experience if this is impacting production systems.

Yes, but I would suggest that you don't take that into consideration yet.

Most attackers break into the servers for reasons such as:

• Perform DOS attacks or C&C of other compromised servers.
• Host copyrighted-infringing content.
• Make political or societal statements by defacing web sites.
• Perform additional compromises to remote servers to clients.

There is no real benefit for most attackers to break into the server just to reboot it. While it is possible, considering the motives of most intruders, it is more likely the issue is something else - either maintenance by the hosting provider, an outage or in the worse case, somebody accidentally restarting the machine and not 'fessing up to it. :)