Why don't you make an investment from your own side and accept one or two jobs for free? Also called a "vouch copy" of your work. This way you will build trust with your future customers.
That is good advice for a newer outlet, but as I said in the OP we have a fairly large amount of past and current clients (which is included in the info-sheet given to potential new clients when they contact us). So, verifying our legitimacy isn't a concern.
But what we didn't want to do was e-mail any of those past clients like "hey got a bitcointalk account? Can you reply to this post for us?". We didn't think that would be professional.
Asking it of someone who found us here however - I think is fine.
Cheers