In case constrained rectangles cannot overlap or contain each other, I suggest putting a slightly smaller rectangle inside every original rectangle. The gap between inner and original rectangle should be small enough that no unconstrained edge could possibly fit inside an original rectangle without intersecting a smaller rectangle. Then, after triangulation is done, delete every edge that is adjacent to any of the vertices of those smaller rectangles. That way you'll be able to find out whether an edge should be deleted in O(1) time, and so the whole procedure will take O(E).
One way to choose a small enough gap is to evaluate the triangulation without smaller rectangles, find the edge of minimum length, and take, say, 1/3 of that length as a gap.