In the first part of your question, you appear to be describing a password hashing scheme. A common (or, at least, commonly recommended) way to construct such schemes is based on a message authentication code (MAC).
Specifically, let $\operatorname{MAC}_K(m)$ be a message authentication code with key $K$ and message $m$, and let $H(s,r) = d = (r, c)$, where $c = \operatorname{MAC}_s(r)$ and the tuple $(r, c)$ is encoded as a string in some non-ambiguous way.
The standard security property demanded of MACs is resistance to existential forgery under chosen-plaintext attacks: that is, even if an attacker is allowed to request $\operatorname{MAC}_K(m)$ for arbitrarily many messages $m$ (up to some reasonable bounds of computational feasibility) of their own choosing, they must not be able to forge a valid MAC (with a probability significantly higher than just by random guessing) for any message whose MAC they haven't requested from the holder of the secret key $K$.
It's easy to see that, with $H$ defined as above, this security property implies that an attacker cannot produce new values $r'$ and $d'$, such that $H(s,r') = d'$, without knowing $s$: to do so, they would have to produce a $c' = \operatorname{MAC}_s(r')$ for some $r'$ whose MAC they don't already know, thus violating the assumption that the MAC is secure against existential forgery.
Generally, we cannot prove that any given MAC is secure in this sense (just as we generally cannot prove the security of any cryptographic primitive, except for some trivial ones like the one-time pad), but there are plenty of MAC functions that have withstood considerable cryptanalytic attention and are generally believed to be secure. Also, what we can, in some cases, do is reduce the assumption about the security of the MAC to an assumption about the security of some other cryptographic primitive, just as we reduced the security of $H$ above to that of the MAC used to construct it.
For example, HMAC, instantiated with a secure hash function, can be proven to be a secure MAC (and, in fact, a PRF), provided that the hash function satisfies some technical assumptions. Of more relevance to password hashing, the PBKDF2 key derivation function can be shown to be resistant to existential forgery, provided that it is instantiated with a secure PRF (such as HMAC). Also, since the scrypt key derivation function uses PBKDF2-HMAC-SHA256 for its initial and final passes, I believe it can also be shown to be existentially unforgeable as long as the SHA-256 hash function satisfies the security assumptions of HMAC.
As for bcrypt, of course its security also cannot be proved, and AFAIK it cannot be directly reduced to that of any other primitive either (except trivially to EksBlowfish, of course). However, neither (AFAIK) has anyone disproved the security claims asserted in the original bcrypt paper. These claims don't directly mention existential unforgeability, but as far as I can tell at a glance, the "$\epsilon$-security" property asserted in the paper does effectively imply it.