The error you're seeing depend on where the gem was installed, if was
installed in user install directory or inside the Ruby version, once
you remove the gem will have this side effect of leaving the binaries.
But as I showed to you, the binaries are inside rspec-core gem, not
rspec, so removing rspec will not remove the binaries.
Dunno if RVM was not interfering in your OSX testing, but if you show
me the exact "gem env" information for both systems I can better
reproduce the issue (if there is any).