Let's assume that Bob is in an orbit similar to those that the Space Shuttle was normally operating in.
In such an orbit, a 200 ft/s retrograde burn was in some circumstances sufficient to deorbit the Shuttle. Depending on the specific orbit, the required delta-v could be as large as 550 ft/s. In civilized units, this corresponds to 61-168 m/s. The rest of the Shuttle's velocity was shedded via atmospheric drag.
MichaelK (who is not me, I promise!) has already mentioned that a good baseball pitcher can pitch 50 m/s.
Sure, as already discussed, it's hard to be a great baseball pitcher when you're wearing a spacesuit. But maybe we can handwave this away by saying that at some indeterminate point in the future, astronaut protective gear has advanced sufficiently to allow something much like that.
We can probably assume that Bob is able to use the spacecraft to prevent himself from being thrown in the other direction. (Bonus: If his tether breaks, and he's carrying these stones, he can just throw one in the direction away from the spacecraft to head back to the spacecraft. See, it's a safety system, and he's testing to see how well it works! It's official mission business!)
The difference between 50 m/s and 61 m/s is sufficiently small that this borders on plausibility. It would be hard, but perhaps not impossible.
Now, the direction he'd have to throw the stone in is counterintuitive. Throwing it downwards (technically, toward nadir) won't work. I'm fairly certain that he'd want to throw it directly retrograde, back the way he came from, possibly at a very slight angle, but Bob would need to discuss the specifics with his flight dynamics officer to be certain.
Also, unless Bob is already in the appreciable atmosphere, the right time to make the throw isn't when he's over Alice's farm, but rather, roughly on the other side of the planet. But this can be calculated relatively accurately, so is not really a problem. Again, talk to the FDO.
So, if Bob's superiors are in on the idea, and he is able to throw the stone in just the right direction at just the right time, with a speed relative to himself (and the spacecraft, hopefully) just slightly higher than that of a good baseball pitch (which places requirement on Bob's protective gear which are not currently met), then he might be able to pull this off.
Unfortunately, the odds that Bob's superiors would be in on the idea are pretty slim, given that this would incur a fair mass penalty on the spacecraft. So he probably won't get a chance to try it. Consequently, as already discussed, Bob, being a practical man, will probably think of some other way to display his affection to Alice.
But it's a nice thought, and it's the thought that counts, isn't it?