You're right, the server needs to send additional unique information, as in http://en.wikipedia.org/wiki/Hashcash

    Server:

    uniq_id = long random string
    salt = long random string
    work_number = random integer
    
    storage[uniq_id] = salt
    send(uniq_id, salt, work_number)


    Client: 

    new_number = work_number

    while hash[:4] != "0000"
      hash = hashfunc(salt | new_number++)

    send(uniq_id, new_number)
    

    Server:
    
    salt = storage[uniq_id]
    if no salt
         deny

    delete from storage[uniq_id]

    if hashfunc(salt | new_number)[:4] != "0000" 
         deny
    else
         allow

May also add timestamps.