Local Search vs Classical Search
Classical local search works as follows. We're trying to optimize some function under some constraints. We start with some feasible point (a point satisfying all constraints). At each step, we consider small changes to the current point which (1) keep it feasible, (2) improve the objective function. If we find such a small change, we modify the point accordingly. Eventually, we reach a local optimum, and we hope that it's not too bad relative to the global optimum.

A classical example is the simplex algorithm for linear programming. The algorithm starts with some feasible point (it's not immediately obvious how to do it; a trick is required). At each step, we try to modify the point by switching one tight constraint with another in a way that improves the objective function while keeping the point feasible. Eventually we reach a local optimum, which turns out to be a global optimum (in this particular case).

The interior-point algorithm for linear programming work differently. They start at some point, and move in a direction that (1) makes the point more feasible, and (2) improves the objective function. In the end, you get close to a feasible local optimum, which turns out to be a global optimum. This is not local search, but it's an example of an algorithm which does not maintain a feasible solution.

Non-oblivious local search is a variant on the theme of local search, in which instead of trying to optimize the actual objective function, you direct the local search using an auxiliary objective function. Sometimes this improves the quality of the local optimum. You can read all about it in a recent PhD thesis by Justin Ward.