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.