I've been thinking about this; I know that piercings can have different rejection rates based on the material of the jewelery, specifically, the smoother the material on a microscopic level the less likely it is to be rejected. In your example, titanium is quite smooth, stainless steel is not, but plasma gold coated stuff is super smooth. I know this is down to the white blood cells trying to contain and remove the 'foreign object' and I'm guessing that this would affect the rejection rate of implants too. If the blood cells were repressed would this not improve the rejection rates?
It has more to do with the atomic / molecular structure of the metal. For example, our body is built to digest and process iron to create red blood cells. It's a nutrient, and therefore, like any nutrient, can cause toxicity if too much is ingested. Titanium is not used by the body in any way, doesn't interact with any enzymes, and doesn't trigger an immune response (unless the person has an allergy to it).
Gold, I think, is very safe, but due to its rarity and cost, it doesn't make a very appealing option. Plus, it's so soft it wouldn't be very structurally sound.