(This is on MMA 184.108.40.206 on OS X)
I've just found a large matrix
m for which
NullSpace[m, Method->"OneStepRowReduction"] give different answers (the first one is the correct answer).
I put the matrix up at pastebin as won't fit here!
What's going on? How might I guess ahead of time which arguments are going to break
(Update; it seems the bug has got worse in 8, rather than better.)