Newton v. Einstein

As mentioned in Death by Black Hole by Neil deGrasse Tyson, both Newton's Second Law of Motion (F=ma) and Einstein's Special Theory of Relativity accurately explain motion in certain environments. Newton's law states that force is equal to the product of the mass and acceleration of an object. This explains most motion here on Earth however Newton assumed that mass was constant. But what if it's not? What happens to a spaceship that constantly loses mass as it burns fuel? What if the mass of an object somehow changes without adding or subtracting matter? This is where Einstein takes over. His famous Special Theory of Relativity describes an object as having an unchanging "rest mass" to which one adds more mass according to the object's speed. When an object accelerates in Einstein's relativistic universe, its resistance to that acceleration increases (showing up in the equation as an increase in the object's mass). So Newton said mass is unchanging and Einstein said it could change. Who was right? As far as I know, Newton's law is ideal in environments with relatively weak gravity like we experience on Earth and Einstein's Special Theory is ideal in extremely high gravity environments such as Mercury, being the closest planet to the Sun and thus experiencing the strongest gravitational pull toward it. Since Einstein's "relativistic" effects only become significant when the object approaches the speed of  light, Newton could not have possibly known about them because the study of the speed of light was after his time.