.. not so long ago, HP ran a contest to find the longest-running HP-unix box in the world. They found one in England which had been running since 1992 without a reboot.
.. wouldn't you love to unplug the power on that one
Anyway, I think it depends on what the server does and how's maintained. In the past, I've had servers running for 3-4 years non-stop, only stopped to be replaced with new ones, but these servers were doing 3 things, and 3 things only, with no updates and no regular users logging in and screwing them up. If you are not rebooting the server, you are not patching the kernel (or if you are, you are risking your kernel getting corrupted).
If you have a server which is constantly having stuff installed and uninstalled, or configs changed, yeah I would say a reboot schedule may be in order, but a turnkey system, not so much.