Where does the force appear when considering object interactions in another reference frame? Imagine I am sitting on an asteroid with my buddy and drinking a beer. When the bottles are empty we throw them simultaneously in opposite directions perpendicular to the asteroid's movement. What will happen?
From the logical standpoint and from momentum conservation, our velocity should not change - the total momentum of two bottles is zero in the asteroid's frame of reference.
Suppose somebody is watching the asteroid from another reference frame (velocity not equal to zero). According to Newton's second law, the force is equal to the change of momentum over time. The mass of asteroid was changed (remember the bottles). The momentum was changed ($M\times V$). Where is the force?
 A: Your analysis in the frame of the asteroid is correct, and the asteroid does not change its velocity.
Unfortunately your analysis in another frame is too simplistic and is incorrect.
Force are applied to objects. When the momentum of an object changes, a force is involved. Here the question is: what's the object?
If the the object is the combination of asteroid and bottle, then the object is destroyed when the bottles are thrown. If the object is just the asteroid, then the mass doesn't really change (except it does, if you had asked this same question but asked where the energy came from for these bottles then you'd have a different question, which has been asked and answered before).
So imagine a simpler example of three particles of equal mass. The left one is moving with velocity $+v\hat x,$ the middle other at velocity $\vec 0,$ and the right one at velocity $-v\hat x$ and they are equally spaced along the x axis. Then after some time they all come together. That moment is like your asteroid plus bottles. Then they bounce off (so now the left has velocity $-v\hat x,$ the middle has velocity $\vec 0,$ and the right one has velocity $+v\hat x$). And none of them need to change their mass. This case is so simple that you aren't concerned.
In your example it's like instead of one particle in the middle you have like $10^{25}+$ particles.  But it's the same deal. They each have a mass and they each have a velocity and none of the masses or velocities change (in my example the bottles are bouncing off so we don't have to ask where their kinetic energy came from, if you want to ask where the bottles kinetic energy came from, I've said that's a different question).
So the mass and velocity of the asteroid alone hasn't changed. And so the momentum doesn't change and hence the net force on the asteroid is zero. Which makes sense because the two bottles exert equal and opposite forces on the asteroid.
And the vekocities of the bottles do change and that's reasonable since they do feel forces.
So effectively what you did is double count the bottles you had bottle before and counted them as the asteroid. And then afterwards you counted them as a separate thing. Sometimes people do a similar thing to see how much force something feels, they look at the change on momentum of momentum to see what force it feels.
But if you had a rocket shooting out propellent for instance then the total momentum is the momentum of the propellent and the momentum of everything else, and it will be conserved and you don't want to double count the propellent even of people oversimplify sometimes.
A: The mass of the asteroid changed, but the mass of the asteroid + bottles did not. Your outside observer would need to include the bottles in calculating total momentum; otherwise the system is not closed.
This is the same principle behind operating rockets in vacuum. We can change the momentum of a rocket by firing out mass (exhaust) in the opposite direction. It's the momentum of the whole rocket+exhaust system that is conserved.
A: The caveat here is that the second law is stated that net force is equal to the change in momentum.
Assuming you and your buddy are not too wasted and are able to synchronize throwing the bottles off with the exact same force, exactly in opposite directions and through the center of mass, the net force is zero, and therefore there is no change in momentum of the asteroid. The momentum of each bottle changes, but they are equal in magnitude, and opposite in sign, and therefore a net of zero.
A: Short answer:
The theorem of conservation of total momentum  (for the entire system asteoroid + the two bottles) can be applied successfully with no contradiction in both reference frames.
In both cases, the result is that the velocity of the asteoroid does not change and there is no net force acting on the asteroid. 
To compare the same situation in the two different references frame, we can use Galilei transformation for the velocity (assuming non-relativistic motion, otherwise use Lorentz transformations).
Detailed explanation:
First of all, some notations. 
Let $xyz$ be a Cartesian reference frame where the asteroid is initially moving at constant non-zero velocity $\vec{V}_{0}$  along the positive x-axis. 
Let $x'y'z'$ be another Cartesian reference frame where the asteroid is initially at the rest at its origin.
Choosing the frame in such a way that, at initial time $t=t'=0$, $x\equiv x'$, $y \equiv y'$ and $z \equiv z'$, 
$$
x' = x - V_{0} t 
\qquad \Rightarrow \qquad 
v' = v - V_{0}
$$
Let $M$ be the mass of the asteroid and $m$ the mass of the two bottles.
We throw the bottles along the $x \equiv x'$ direction, in such a way that, in the frame $x'y'z'$, the two velocities are equal and opposite, ie, $v_{1}' = - v_{2}'$. 
So, the total momentum $P_{0}'$ and $P'$  (in the frame $x'y'z'$) before and after throwing the bottles  are respectively given by
$$
P'_{0} =  (M + 2m) \cdot 0  = 0
$$ 
$$
P'  = M v' + m v_{1}' + m v_{2}' =  M v' + m v_{1}' - m v_{1}' = M v' \; ,
$$ 
where $v'$ is the velocity (in the frame $x'y'z'$) of the asteroid after throwing the bottles. Since there are no external forces acting on the system, 
$P'_{0} = P'$ and thus $ v' =0 $. This also implies that there is no net force acting on the asteroid itself.  
What happens instead in the reference frame $xyz$? The initial total momentum is in this case
$$
P_{0} = (M +2m) V
$$ 
(because both the asteroid and the two bottles are moving at speed $V$ at the beginning) and
 the total momentum $P$ (in the $xyz$ frame) after throwing the bottles is 
$$
P  = M v + m v_{1} + m v_{2} 
$$ 
where $v$ is the final velocity of the asteroid and $v_{1}$ and $v_{2}$ are the final velocities of the two bottles. 
But in the $xyz$ frame $v_{2} \neq - v_{1}$
Explicitly, 
$$
v_{1}' = v_{1} - V_{0} \qquad
v_{2} '= v_{2} - V_{0}
$$
and thus $$v_{2} = -v_{1} + 2 V_{0} \neq -v _{1}!$$
This is the key point: the two velocities can't be equal and opposite in both frames. 
So,
Again, there are no external forces acting on the system, thus $P_{0} = P$, yielding $v=V$. The asteroid does not change velocity and no net force acts on it. 
Few Remarks:


*

*The same reasoning applies to the relativistic case, the physical meaning is the same, but you have to replace Galilei transformation with Lorentz transformation;

*We can apply the law of conservation of moment when there are no EXTERNAL forces acting on the system. 

*We can't apply $\vec{F} = m \frac{d\vec{p}}{dt}$ naively to a composed system which exibits a time-dependent mass. 
It's easy to see that this would violate the Galileain invariance and would lead to wrong equations of motion (as a prototypical example, consider the rocket equation in free space)

A: The technical answer is that the force "comes" from your buddy and you, who spend (chemical) energy to throw the bottles.
If we consider an idealised scenario, though, where a system of three glued points breaks suddenly down, then I will argue that there is actually no change in the momentum => no need of force:
1) Before the break-down the system's momentum is:
$$\vec{P}(1) = \vec{P}_{A}(1) + \vec{P}_{b_1}(1) + \vec{P}_{b_2}(1) = (M_A + m_{b_1} + m_{b_2}) \vec{V}$$
2) Suppose now that the balls $b_1$ and $b_2$ (I suppose they have equal masses) are thrown at opposite directions relative to the asteroid, say $\vec{v}$ and $-\vec{v}$. Therefore:
$$\vec{P}(2) = \vec{P}_{A}(2) + \vec{P}_{b_1}(2) + \vec{P}_{b_2}(2) = M_A \vec{V} + m_{b_1} (\vec{V} + \vec{v}) + m_{b_2} (\vec{V} - \vec{v} ) =  (M_A + m_{b_1} + m_{b_2}) \vec{V} = \vec{P}(1) \Rightarrow \triangle \vec{P} = 0$$
I've noticed that you worry particularly what happens with the asteroid (on its own). Then the answer is similar:
$$\vec{P}_A (1) = M_A \vec{V} = \vec{P}_A (2)$$
i.e. no change in momentum. I suppose your confusion comes from the fact that you initially consider the momentum of the asteroid as the total momentum $\vec{P} = \vec{P}_A + \vec{P}_{b_1} + \vec{P}_{b_2} \neq \vec{P}_A$ ;)
