thanks for your response. Could you please provide a link to a good step-by-step guide on how request an address in a trustless way? Thanks.
1) Generate a Bitcoin address, save its private key safely, find out its public key - use
http://casascius.wordpress.com/2013/01/26/bitcoin-address-utility/ or
https://www.bitaddress.org/ for example (you will need those services later anyway)
2) Fill out the details in
https://vanitypool.appspot.com/newWork3) Send the request, send the bitcoins to the specified address
4) Once your work is solved, use the tools from point 1 to combine the key
5) Import the key into your wallet of choice
Best start with a simple and cheap pattern to get the hang of things.