From what I can tell the biggest problem with mines is the sheer ungodly amount of them the AI uses, especially in later, longer games.
A few mines are nice, but the hundreds upon hundreds, make advancing forward in larger games a tedious chore, and seem to bog down the game speed in the latter 1/2-3/4's of larger maps. (and I'm running a dual core processor with specs well above the reccommended)
Perhaps adding in an option to "turn off mines" when creating a game would work best, allow players to choose whether or not they want mines for those longer games. (similar to how we can turn pirates on/off when setting up a game.)
Don't get me wrong, mines are a fun tactical addition to smaller maps, but on the larger ones they just detract from the fun factor and bog down an otherwise enjoyable game.
Edit: I also suspect the insane amount of mines on larger maps is what causes the desynch issues so many of us run into.