I tried a few variations on the maya.env file, including deleting all the contents (which is the working default for other users). I then reinstalled the software and it now works fine. When I also replaced the maya.env file with what I had before it still works. So my guess is that something had been corrupted or deleted.
The full text search for MAYA_LOCATION yielded quite a few items. Mostly docs, but also libs, dlls and a few location sensitive mel scripts. There was some other stuff but nothing that seemed to be setting an environment variable.
So what is setting the variable? Well, starting maya from a different location doesn't change it, so it's not on that basis. My guess would be that it's assuming a default location, like C:Program FilesA..W..Maya4.X. Only setting that as the MAYA_LOCATION directory when the problem arose did nothing to solve it. Anyway, at least it's working now.