OK, use cases:
1) IMMEDIATE - normal case, where you want blocks re-lit as they're placed.  Heaviest on CPU, will cause lag for large changes.
2) NEVER - maximum performance.  But, as @Wolvereness and yourself pointed out, things can just look "wrong" (although the client seems to do a pretty good job at compensating for that when you get close to updated blocks, I guess that's an implementation detail that can't be relied on).
3) STATIC - for "flood-lighting" areas, such as game boards (my ChessCraft plugin is part of the reason I'm working on this).  Where you want to keep a given area at a given uniform light level.
4) DEFERRED - for very large changes, where you want to smooth out the load of re-lighting.  Lighting is done over several ticks.

So I admit NEVER may have to be ditched (fast but wrong isn't good enough), STATIC seems pretty useful to me, and IMMEDIATE/DEFERRED could potentially be merged, but the following need to be considered:
* DEFERRED could be the default approach here, but a good threshold value needs to be determined for the maximum time per tick that a server can spend doing re-lighting work.  Whether or not this is tunable by plugins is up for discussion.
* IMMEDIATE could be dropped entirely and made simply a special one-tick case of DEFERRED.

That would then boil down to a choice between static lighting and natural lighting (with a possibly tunable "aggressiveness" factor).