I have a theory as to exactly what MiB is referring to when he says he wants to go home. I believe his "Home" is actually the X-reality, and I would like to explain why.
To explain why, I need to briefly talk about MiB's offer to Sayid, but bear with me. To refresh you, MiB made Sayid an offer to give him anything he wanted in exchange for his help, and Sayid seemed to imply that the one thing he wanted is gone, most likely talking about Nadia. Now, it has been my belief all along that the way MiB is able to make such an offer is simple: MiB knows a way to open a porthole into the X-reality. MiB isn't offering to revive Nadia's dead body - he is offering Sayid a way to swap conciousnesses with his X-counterpart, so Original-Sayid can live in a reality where Nadia is actually alive.
So, what does this have to do with the title of your blog, you ask? Well it's my belief that MiB also wants to swap his own concsioussness with his X-counterpart. Every time someone refers to MiB as a "what" he corrects them and tells him that he is a "who" and that he used to be a man, too. And so it is my thinking that MiB wants to once again be a mere mortal, a man, and escape his immortal monstrous body, and allow his consciousness to enter an alternate version of himself that exists in a parralel universe. In this parralel universe, he is a man, nothing more nothing less, and he wants to be a mortal again.
The only trouble with swapping his consciousness over like this, is that wouldn't this still trap an alternate-universe version of himself in the Smoke Monster's body? Well, Yes, it would! I believe this is why MiB says that he is trapped. This has happened to him before - and he is now trapped in the body of the Smoke Monster. He used to be a man, a mere mortal, until his conciousness was dragged across space and time and entered into the Smoke Monster. Since that time, he has been searching for a way to escape the body of Smokey.
An alternate version of himself trapped him in this Smoke Monster, and now to escape, he wants to do the same to another alternate version of himself. So even if our well-known, Titus Welliver/Terry O Quinn played MiB manages to free his consciousness and live inside his mortal body in a parralel universe, the Smoke Monster will still be alive, occupied by another mind. This perpetual cycle keeps the balance of good and evil on the island. This perpetual Smoke Monster means there also needs to be a perpetual protector of the Island, so up step The Candidates.
Whoever the new candidate is, he will have to deal with the Smoke Monster for the next couple of hundered years, in the new cycle of balancing good and evil. I believe the exact moment MiB manages to swap conciousnesses will be the exact moment that a new candidate is named, and so starts a new cycle of a battle between The Smoke Monster and The Islands protector.
To further back up this theory, notice how in the episode "Dr. Linus", MiB still says to Ben that there needs to be a protector of this island. Now if MiB were just running away, why would he care who protects the island? Well, MiB knows that even after he leaves, that the prophecy still lives on, and that the balance still plays out. There will always be a Protector and a Smoke Monster.
And as of the rules? Well perhaps the rules are that you can kill, but you can't kill eachother if your conciousness's are from seperate universes, as this will somehow screw up the time-space continuum (I admit, that it isn't a fully formed explination of the rules, but it still could work). Smokey might have no problem with killing, but even he isn't silly enough to commit a killing that would destroy the universes, and hence himself.
MiB is currently assembling a group to "leave the island" but I'm not so sure it's going to be as simple as hopping on a boat. I believe he is going to use the power of the island and offer them the chance to temporally displace themselves for good, thus bridging the two timelines we currently have. Once he's done this, I believe he will temporally displace himself, and enter into the X-reality, to live out his days as a mortal once more.