Since you mentioned "the obvious answers" I thought I might repeat one of them: search the literature. As a new graduate student I starting working on a problem and even solved a neat special case, but then came to find out that it had appeared about 20 years earlier.

Fortunately for me, this didn't discourage me, and I started working on a harder case. Strangely enough, about the next week my advisor told me of a conference he had just gone to in which it was announced that this harder case had been solved! So I guess method two might be: know who is working on these problems, and attend conferences. Talk to the experts and see what they think about the problem.

Again, fortunately this didn't discourage me and I delved into their proof, found an unfixable hole, and eventually found a correct proof.

To be frank, sometimes it is a good thing to work on the same problem as someone else. You get your own intuition about the problem. But if you worry about being scooped, and need publications, try method three: work on a problem that is very specialized, and not highly publicized.