I'm planning a Turn Based Strategy game written in OpenGL and need some advise on the approach. It will use things like MD2 models and will be somewhat in the mould of XCom - Enemy Unknown (so, an isometric approach). Now, he's the thing - Since the maps are going to be randomly generated from a load of predefined tile sets and given that the game isn't going to be over frantic with dozens of collision checks, etc... so, Would using BSP be complete and utter over kill and over complicate matters? Anyone done a game of this sort using the above approach?

Yes, BSP would be overkill. You got a nice and clean tile structure, so why not use that tile structure as a partitioning system (which it already is) ?

Or even better, you could use a quadtree that is always easily added on top of a tiled map.