To answer your specific questions,
Is it accurate that pressurized air directed on the skin can cause an embolism? ... Are there any documented cases of this having happened?
Yes, there is at least one documented case. I found it in the OSHA (US Occupational Safety and Health Administration) industrial accident database using the keyword "embolism" and scanning through the data for any mention of compressed air. The accident summary states:
At 8:30 a.m. on May 20, 2019, an employee was using a compressed air gun to clear a paper jam from a Gambini Rewinder Machine. The employee lost his grip on the air gun and cut his hand. The laceration to the employee's hand caused an embolism to form requiring hospitalization.
This is the only case I found, so it appears to be fairly rare.
OSHA Nozzle Requirements
The "special nozzle" that your workplace requires is described in OSHA standard 1910.242(b):
Compressed air used for cleaning. Compressed air shall not be used for cleaning purposes except where reduced to less than 30 p.s.i. and then only with effective chip guarding and personal protective equipment.
This is further clarified in OSHA Instruction STD 01-13-001 - STD 1-13.1 October 30, 1978 which states:
The phrase "reduce to less than 30 psi" means that the downstream pressure of the air at the nozzle (nozzle pressure) or opening of a gun, pipe, cleaning lance, etc., used for cleaning purposes will remain at a pressure level below 30 psi for all static conditions. The requirements for dynamic flow are such that in the case when dead ending occurs a static pressure at the main orifice shall not exceed 30 psi. This requirement is necessary in order to prevent a back pressure buildup in case the nozzle is obstructed or dead ended. See enclosure (1) for two acceptable methods of meeting this requirement. Also, there is no intent to restrict the diameter of the nozzle orifice or the volume (CFM) flowing from it.
It appears that the standard is intended to ensure that the pressure on the skin when the nozzle is fully obstructed by a body part is no greater than 30 psi. The standard does not prohibit higher pressures in unobstructed nozzles.
Embolism Risk
While there are a number of sources that mention the risk of embolism, I didn't find that in any OSHA documents. I did see it in an Oregon OSHA fact sheet which says that compressed air can enter the bloodstream through an existing wound.
Compressed air can enter the body through a scratch or small puncture wound and cause swelling and severe pain. If the air gets into the bloodstream, it can cause an air embolism, which can cause symptoms similar to a heart attack or a stroke.
In the OSHA accident report cited above, the embolism occurred as a result of the employee lacerating his hand, and not by compressed air entering through the skin.
I spent some time looking for a basis for the OSHA 30 psi requirement, but was not able to find anything. Perhaps someone else will be more successful.