Your black hitchhiker could be a number of things -- it will be hard to ID without a photo. There are several totally different animals that are black in color that are known to hitchhike on rock or coral into reef aquariums.
The first two possibilities are snails, although most people assume that they are slugs when they first see them. There are black stomatella out there; in fact, there have recently been a few post regarding them, so you may want to search RC (or just look at the threads in this forum from the past week or so.) Another black snail hitchhiker are the Scutus spp. snails. They have black fleshy mantles that cover their white shells, and thus look slug-like.
There are also two common dorid nudibranchs that feed on sponges that are sometimes found in aquariums: Dendrodoris nigra and D. fumata. It could be this nudi's rhinophores that you describe as "long black SPS polyps on its back" (I don't know what else to make of that description.)
If none of these match your hitchhiker, than I suppose it could be a cowrie of some type, as they have mantles of different colors as well, and some have projections and such. Beyond that, I'm out of ideas, but maybe someone else will have some.
EDIT: if your hitchhiker is any of the named animals above, I wouldn't remove it from my tank. The two snails are herbivores and the nudibranchs feed on sponges and will likely starve eventually, regardless, so you might as well enjoy it and let it go about its business while it can.
