I came across a random solution today that everyone should know about.
If you are using Camera Based Selection to select Verts or Edges, sometimes when you marquee select it will only select a few random vertices - not the ones you were planning on selecting. This was extremely frusterating because it seemed the only way to select the verts you want is to turn off Camera Based Selection, and have to deal with selecting verts that you didn't mean to.
For me, the problem was solved by turning OFF "Wireframe on Shaded" mode. I've tried it on a few computers in my lab, and it seems to be the same across the board. Again - if Wireframe on Shaded mode is ON this bug seems to occur.
I don't know why this is happening, but at least I found the problem. Can anyone confirm this problem/propose a solution? It seems like a bug in Maya, not a preference issue.
Just returned to sadly say that the solution doesn't always works (I'm having the same problem again). Well...