Faster DDR memory should always work in a system that only supports slower clocked memory - it's part of the spec. However you do have to stick with the stated type (ie DDR3\DDR2\DDR). I would generally advise someone to buy the correctly rated memory but if all the parts are built to spec then there should be no issue using faster rated memory in an environment that underclocks it.
The server CPU's you mention are part of the entry level Nehalem Xeon 5500 series, along with the L5506, L5508, E5502 and E5504 they are specified to support a maximum memory speed of 800Mhz. The next bump up in the Nehalem range (the E5520, E5530, E5540,L5518,L5520 & L5530) support 1066Mhz & 800Mhz DDR3. The two higher end ranges (the X5550,X5560,X5570 & the W5580 and W5590) support 1333Mhz/10666 & 800Mhz.
The higher speeds generally impose limits on the maximum amount of memory you can add to the system - in general for the Xeon 5500 range at 1333Mhz you are limited to 1 DIMM per memory channel, and at 1066 you are limited to 2 for most systems. Some Server vendors (IBM & Cisco) have motherboards that can exceed those limits. There are some further limits imposed depending on whether the DIMM's are Quad\Dual or single ranked.
The Xeon 5500's don't absolutely need ECC memory, the CPU's on chip memory controller does support unbufferred DDR3 aswell as both registered and unregistered ECC DDR3 but it's always a good idea to use ECC memory in Servers. For a specific system you need to check that the motherboard also supports the memory type that you wish to use. The choice of Registered\?Unregistered\Unbuffered memory also affects the maximum DIMM per channel limit - you can only support the maximum RAM configs with the Registered ECC memory @ 800Mhz for example.
There is a very good overview of the memory types supported by the Xeon 5500 series on this Intel site.
As far as availability goes - the various Server vendors all supply parts rated at these speeds for their platforms but they could well be supplying higher speed parts and running them at lower clock speeds. For reference Crucial's memory config utility only lists 1066 & 1333Mhz options for the Dell R610 which can be configured with the full range of Xeon E\L & X variants of the 5500 Xeon series CPU's.