There are indeed two options, the one where you have to trust us and the security of our server is just there to quickly test the procedure or for small amount addresses.

In both cases, the private key we send you is not the final private key, you still have to combine it with your own private key. Since we don't have that one, your address is safe.
The combination procedure is described in the solution email. I suggest you try to order a free address to see how it all works