Check if two anonymously signed messages have the same author
Ok, here's a simple method that appears to address your requirements.

It uses two signature methods; the first one (the "inner signature") is conventional; the second one (the "outer signature") is anonymized.

When Alice generates a message $m$, she either generates a public/private key pair $Pub_a, Priv_a$ for the inner one, or reuses a $Pub_a, Priv_a$ pair that she previously generated.  She then signs the message with the private key, generating $Sig_a(m)$, and forms the tuple $(Pub_a, Sig_a(m))$.  When then interacts with server to anonymously generate the public signature of this tuple $Sig_s(Pub_a, Sig_a(m))$, and generate as a signature the tuple:

$$Sig_s(Pub_a, Sig_a(m)), Pub_a, Sig_a(m)$$

To validate this signature, one would verify that $Sig_s(Pub_a, Sig_a(m))$ is a valid signature for $Pub_a, Sig_a(m)$ (based on the Server's public key), and if $Sig_a(m)$ is a valid signature of the message (based on the public key $Pub_a$).

As for your requirements:


It is anonymous; $Pub_a$ is a random public key, and so there's nothing to link it with Alice
It is linkable; Alice can use the same $Pub_a, Priv_a$ to sign two related messages; anyone can see that those two signatures use the same $Pub_a$ value (and hence must be signed by the same person)
Links are trustable; as no one else knows the value $Priv_a$, no one other than Alice can sign a message using $Pub_a$