Momentum conservation doesn't automatically follow from translation invariance. That only happens because of special features of physical laws, so if you want to prove that translation invariance implies conservation of momentum, you'll need to use some principles of physics to do it. Make up new laws that break those principles and you can indeed have translation invariance without momentum conservation.
The principle you need is called "least action". You need to be able to write the physical law in a way so that it's minimizing something, like, for example, light taking the fastest path between points (and minimizing travel time). This is a simple example of what to minimize; others are more complex.
In general we create a function called the action that takes as its inputs the history of the entire physical system over some time and outputs a number. Whichever motion of the system minimizes the action subject to some boundary conditions is the true motion.
Most physical laws can be written this way, including Newtonian gravity. Your law, though, can't. The reason is we can't come up with an action that makes sense. If the formula for it involves $m_a m_b^2$, well, one problem is that the universe has no way to decide which mass is which, so it would be very strange indeed!
Even if there were a way to decide the one on the left is "b", for example, we'd be stuck with that. That one on the left would always be the one that's squared. In your proposed law, we always square the "to" mass, but the action formula, even if it knows the masses are different, has no idea which one is "from" and "to", because it can only see the entire system. You couldn't get from least action to a way to treat the masses with this particular asymmetry.
So you're right. That law does violate conservation of momentum and it does have translation invariance, but the piece you're missing is that it's a strange law that doesn't obey some basic rules that real laws do.
The most-accessible introduction to these ideas is in Feynman's The Character of Physical Law, or this lecture he gave: http://www.youtube.com/watch?v=zQ6o1cDxV7o The argument of interest comes near the end, 45 or 50 minutes in.