For the figure on page (18) it was generated with SH9 baked into light map texels. However, you're approach with a grid will work as well if it's dense enough.The occlusion will come naturally and there are no additional techniques you need to apply because at every position in shadow the cubemap will receive less light.
This works for both diffuse and ambient.
I suspect the reason you aren't seeing any occlusion is because you are adding an ambient term artificially flattening out the scene.
I've also noticed these weird arfiacts on my light probes. Is this "ringing"? Or am I just really messing up the projection step?
If there is a bright light on the opposite side of the probe then yes. Ringing can occur when you have a bright light on one side which causes that side of the probe to generate really high numbers. On the opposite side of the probe facing away from the light it will need a really high negative number to counter act the high number.
The negative numbers are the cause of the ringing