So, now two complete strangers that I know nothing about and have no reason to trust each have a different half of my private key, and I'm supposed to feel "safe" about that?
These two strangers will only have 1 part of the full private key, i.e. no stranger can get a full private vanity address key. In this, the whole point is that parts of the private key are kept by different strangers. In fact, they must collude in order to get a full private key, but then they both lose trust from the side of other users.
Furthermore, the first stranger will be sharing his half of my private key with lots of other people (so they can all get vanity addresses generated with the same effort by the second stranger).
No, after a vanity address was generated for some customer, a new public key obtained from a third-party service is used for the new customer, because a private key from a third-party service can be obtained only 1 time (see post#9).
Now, lots of people all have one half of my private key, and the vanity address generator has the other half. Furthermore, depending on the method used by the vanity address generator, it may be possible for someone else to use their vanity address partial private key from the same generator to calculate mine?
No, only you can get the full private key of your vanity address. And with an insignificant amount of probability, the full private key of your vanity address can get by "strangers" if they enter into collusion, but they both lose trust from other users.