You are totally right: unused addresses wont link over there. I just checked with a fresh one and it says "Address 15FsNoLgZg9FgkKhVFhjnYEsoD3o8d4yCg not found. Note that database is not online; if address was used too recently, then is cannot be in our database yet."
You'll never be able to link a Paper Wallet, much less a vanity wallet address that hasn't been imported into a wallet. (even on using a part public key) unless it has some outgoing connections.
AFAIK the only way one can link wallet addresses to one another is when their inputs are used in a single transaction -- example is if I use an input from 1Act... as well as 1PNG... to send bitcoins to a single output. Otherwise I don't think there's any way to link them. (correct me if I'm wrong)
If you're smart about it and only use inputs from distinct addresses there is no way to link them. Right?