Many problems can always be solved with a bit of decomposition.
First off, if your target is the MMO space, then I suspect you either elected to create your maps in continous connected zones much like World of Warcraft's world maps are designed or they're separated into zone-based maps much like GuildWars2.
In either implementation, a map includes area triggers that signify sub-areas or sub-zones within that map (terminology is entirely up to you). So if you combine the characterId, mapId, and areaId; that can easily describe an entry in an exploration table on the server side.
When a player enters a particular map, it's the server's job to query this exploration table and send the client information about what the player has already explored so it can update it's world map state, etc. As the player navigates throughout the world, the area triggers fire and check whether the player has ever visited the area. If so, nothing happens. If not, the server updates the player's exploration state, sends a packet to the client so that it can do the same and perhaps inform the player they've discovered the new area. At some checkpoint on the server side, the exploration data held in memory will be committed back to the database.
Such a narrow table can easily hold millions of rows with little overhead. But it's important to note here that it's the server's job to detect when new areas are explored and to simply send visual information to the client. In no way does the client update any of this state on the server. It's all transparently done based on the player's current position in the map and the area trigger objects defined by the game map design team.