But of course my geometry has none...
Easy fix, calculate the normals on the fly when they are needed!
Sample the points surrounding the point on the surface.
This gives 9x9x9 points (if you include the point itself).
For each of these points, if it is filled, move the normal away from the sampled point.
Doing this I have managed to achieve a very nice collision response to any point on the surface.
(Its awesome =P)