I'm looking at using the following part, S4PM: Datasheet
The part has a Vrrm of 1000V. The mounting pad layout shows a separation of 0.81mm between cathode and anode.
This is well below IPC2221B clearance for 1000V (should be 2.325mm, for a coated board). How can this part be rated for this voltage?
It can be rated for that voltage because it is not a coated FR4 circuit board. As you've said yourself as part of your question, the 2.325mm clearance as stated by the IPC2221B standard is for a 'coated board'.
The epoxy encapsulation needs no such clearance, it will withstand 1000V with that much distance just fine.
Now, you're probably thinking, "but it will be soldered to a circuit board."
Yes, it will. Make sure you cut an isolation slot underneath it. The 2.325mm clearance is for a continuous PCB, not for a PCB with a slot cut in it providing an air gap. Air can withstand around 3kV per mm, so even a tiny slot will withstand much higher voltages than that same width but occupied with FR4.
You can also cut a groove, this image (which I've blatantly stolen from Andy Aka's answer to this question), should give a better idea of how you can effectively meet the IPC clearance while still having two pads closer to each other than that clearance.
Also, make sure you use rounded pads. Arc over is dependent on electric field strength, and sharp corners will concentrate it whereas smooth rounded edges will spread it out.
