I understand the value of some form of edge/point/face dissolve - they are on my list of things to do. But I don't know when I'll get to them.
It's not clear how to implement them however. It's easy to introduce convex faces which are invalid faces. nemyax there are several in your examples that won't properly render. So I'll describe this in a bit more algorithmic manner what I'd propose:
For edge dissolve I'd propose something like your with clean-up:
1) Find connected groups of faces that are adjacent via a selected edge.
2) Delete all selected edges and and adjacent faces.
2) If any end points are left without any edges attached, delete them.
3) Rebuild faces from connected groups. There are a lot of possible problems: one example of many is if a ring of edges completely encircle a group of faces, then deleting them will create an island. If anything strange like this is present, bail out and revert to the original mesh.
4) Convert any sequence of connected edges that are part of the same two faces into a single edge. (This is the "with clean-up" part.)
For point dissolve:
1) Selected points with 0 or 1 edge are deleted.
2) Those with 2 edges are replaced by a single edge. Adjacent faces, if any, are rebuild accordingly.
3) For those with 3 or more edges and have two edges each (i.e. a properly built mesh), delete all the edges and add a new face as above. Again multiple problems can arise, such as islands. These will cause Anim8or to bail-out.
For face dissolve:
1) Replace each selected face group and all it's edges and points with a single point at the group's center.
2) Rebuild adjacent faces with this new point in the place of all their deleted edges.
3) Delete degenerate faces (i.e. those with only two edges).
Then there's the concept of face and edge collapse, which is another topic ...