> Say it eats an atom - it has to accelerate that atom to the same relativistic velocityNot quite the same, but almost, yes. The final velocity of the hole after it eats the atom will be equal to the velocity of the center of mass of the hole + atom before the atom is eaten. But if the hole has the rest mass of Mount Everest, the motion of the center of mass of the system will be almost the same as the motion of the hole, since the rest mass of Mount Everest is probably about 40 orders of magnitude larger than the rest mass of an atom.
> meaning that new atom now has EXACTLY the same gamma as the black hole
Yes. But this gamma will be slightly less than the gamma of the hole before it ate the atom.
> and steals just as much momentum as if gamma was 1.
I see what you're thinking, but it's still wrong; you haven't calculated the effect correctly. See below.
> It only needs to absorb mass similar to its own rest mass.
No. Say the hole starts out with rest mass M, and is moving at velocity v, where v is almost 1 (the speed of light), so the gamma factor is, say, 1000. Then the total momentum is about 1000M.
Now the hole absorbs enough atoms to have rest mass 2M, and each atom is at rest before it's absorbed, so each atom contributes zero momentum to the total, so the total momentum is still 1000M after all the atoms are absorbed. That means the gamma factor is now (to a very good approximation) 500 (rest mass 2M times gamma of 500 times v approximately 1 gives momentum 1000M), which still corresponds to an ultrarelativistic velocity.
For the velocity to be less than Earth escape velocity, the total momentum of 1000M would have to be carried by a hole with a rest mass of about 3 million M, since Earth escape velocity is about 1/3000 of the speed of light (11.2 km/s vs. 300,000 km/s)--i.e., we would have rest mass 3 million M times gamma of approximately 1 times v of 1/3000, to give total momentum 1000M.
> That is also irrelevant. The only thing that matters is its "width", i.e. how many of the particles it interacts with does it eat.
The cross section (what you are calling "width"--what fraction of particles encountered does the hole eat) will depend on the speed of the hole; the faster the hole is traveling, the lower the cross section will be.