Is it possible that, given that we know there are alternate realities (flash sideways), that MIB is in fact Jacob's mirror opposite in another reality? Jacob is obviously "gifted" in some capacity and has a unique relationship with the island. Is it possible that the island is a sort of Woods Between Worlds (ref. CS Lewis Narnia series) that allowed LOST reality Jacob or possibly all "Jacobs" in all realities the ability to "see" other Jacobs? If so, LOST reality Jacob discovers his negative counterpart, realizes nega-Jacob's plan to bring about an "Omega Point" in his own reality - thus destroying the rest of the realities by proxy, and devises a plan to "jail" him in LOST reality in order to try to convince him not to carry out that plan? This would explain the "rules" in that they are each others' "constants" - killing the other directly would cause madness and death from forcing separate memories of dual realities on the perpetrator (thus, MIB searching for a "loophole"). It would also explain MIB's desire to "go home" (to his own reality). It even explains why we don't hear MIB's name and why he is only referred to by Jacob and by himself as "a friend" - his name is likely also Jacob.
The black smoke is the embodiment of evil, present in all realities and able to cross into multiple dimensions (like Stephen King's recurring "Flagg" character). At some point MIB made an agreement with and merged with the black smoke in LOST reality in order to kill everyone in Jacob's village with the intent that it would force Jacob to let him "go home". However, the plan backfired as it only reinforced Jacob's conviction to keep nega-Jacob jailed until he could "prove him wrong" about the existence of pure good in the universe.
The Dharma Initiative represented a paradox to the Jacob/MIB conflict: people attempting to do pure good but doing it for the reason that people are inherently bad and will bring about the end of time and space through evil deeds (Valenzetti equation). This creates the paradoxical cycle that leads to the release of the island's energy, the 815 crash, time-skipping, and, ultimately, the "loophole" that allows for Jacob's murder.