Communicated-Key/Token for SOAP Authentication

Hi all, I'm working on a relatively straight forward Web API that'll have a SOAP presence. The most secure way of going about doing authentication would be undoubtedly client-certificate authentication. I have been able to implement such a service straight forward as there is plenty of documentation out there covering how to do so. I have some clients who're reluctant to manage client certificates at this point in time, and do prefer a communicated-key authentication, very similar to what Amazon and a few of the other big boys do. I'm having a bit of a difficult time coming up with multiple solutions as to how to properly implement this for my service besides stuffing a random hash into my database and making them send it to me over SSL through their message payload. I can then compare the hash against what's in the database + their IP, or something else. Would anyone be able to suggest some algorithm for the way I'm handling the tokens that's more secure and less "brute-forcible" than the methodology I described above? My objective in this exercise is not to only authenticate who's sending me the SOAP envelope, but also to ensure that whatever token/key system I implement is not open for very simple brute force. If they're able to knock down my brick house, I have other problems --- but I definitely want to build that brick foundation. Suggestions, web articles, books etc., are all welcome! Thank you for any advice from you avid web service gurus. /sf