Is my authentication system adequate?
They do md5(random_string + password), and send this and the random string along with their data. 


What would happen if the attacker recorded the above data, and then sent 'md5(random_string + password)', 'random string' (both from the recorded data), and then included their preferred data.  The system would check that the random string checks out, and so trust the data.

What I would recommend is something like:

HMAC( random_string, data ), data


(where data would include something that would identify the client, if necessary)

That way, the attacker can't just cut/paste the authentication information; it is a function of the data being authenticated.

BTW: there is no reason to use MD5.  The weaknesses known in MD5 do not apply in your case, however that's not a good enough reason to use it; I'd suggest using SHA-256 instead (possibly truncating it if 256 bits is too long)