some kind of dynamic and localized subdivision surface modifier - type algorithm?
Well, as I originally suggested in the previous question, you can always try using the Remesh modifier.
It dynamically generates a clean mesh with ~equal size quads out of the volume of your mesh.

I'd recommend using the smooth mode and an octtree depth of 7 or more to get accurate reconstruction of your mesh.

ADDED: It also helps to add a smooth modifier on top of the remesh modifier, because the mesh generated by the remesh modifier is still a but funky due to the issues with the original mesh.



Here's a code snippet you can add to your script:

myObject.select = True # Replace myObject with a reference to your actual mesh object
bpy.context.scene.objects.active = myObject

bpy.ops.object.modifier_add( type = 'REMESH' )
m = bpy.context.object.modifiers['Remesh']
m.mode         = 'SMOOTH'
m.octree_depth = 7

bpy.ops.object.modifier_add( type = 'SMOOTH' )
m = bpy.context.object.modifiers['Smooth']
m.iterations = 26


It's not exactly what you asked for, but might do the job nontheless.

ADDED: You only need to add this modifier once, of course (it will adapt to changes in your mesh), but it will slow down your script considerably, since the remesh modifier takes quite a bit of time to calculate, especially in the higher octtree_depth levels.