Broken SELECT in Sql Server Compact 3.5 SP2?
I can only guess that the problem is related to some sort of index
  corruption - maybe it gets out of sync with the actual data store.


You could isolate index issues by just dropping the index. That will slow down some or all of the queries that access that table, but if the problem goes away, you know for certain that the index was the source of the problem.

But even if the index is the source of your problem, it's not the root cause of your problem. To my way of thinking, the root cause is quite likely to be in Microsoft's code. An index that doesn't match the data is one of those things the database shouldn't allow. And if it happens, you should see big, waving red flags.

You can verify and and try to repair a SQL Server CE database in code.  I'm not sure whether this exercises the same code you'd use by trying to repair through SSMS. (I'd hope so, but I know that hope doesn't scale well.)

How to: Verify and Repair a SQL Server Compact Edition Database (Programmatically)


  I think it might have to do with modifying the db from different
  threads (at some points we may have 2 threads working on the db), but
  I thought this shouldn't be an issue.


Documentation for .NET 3 SqlCEConnection class.


  Any public static (Shared in Visual Basic) members of this type are
  thread safe. Any instance members are not guaranteed to be thread
  safe.


I think you're safe if each thread uses a separate connection. I could be wrong.