I have seen one other case with this behavior but I doubt it is causing your problem.

I frequently use "select with constraints" to determine if I have n-gons, non-planar, non-manifold geometry.

I just as frequently forget to uncheck the thing I am trying to select for then invariably scratch my head for 15 minutes before I realize I have select only non-planar or something checked and maya refuses to select anything.

But as you are clearly leaving and restarting maya any select with constraint options would be reset.

I am still thinking about it though and if anything comes to mind I will post it.

Have you changed any hardware, gfx drivers, gfx cards, in particular? I hate to fall back to the old "Have you reinstalled maya?" recommendation but...