Given the existence of provably-hard-to-solve problems, why do we routinely rely on conjectured-to-be-hard problems for encryption?

Let $(X, Y, Z)$ be a set of binary strings of length $n$. Let random $X$ be the private key for encoding (or decoding) message random $Y$ as $Z$. Let the encryption algorithm $m$ be a matching function, i.e., for $m(X, Y) = Z$, if $x_i = y_i$, $z_i = 1$, otherwise $z_i = 0$. Now, $m$ is clearly not a one-way function: given output $Z$, it is trivial to define some string pair such that $m(X, Y) = Z$. However, it is impossible to obtain the particular encoded message from the encrypted message without the private key.

Reusing the key repeatedly does not compromise it, given that $Z$ provides no information (entropy) about $(X, Y)$. To wit, suppose an eavesdropper collects a set of $k<2^n$ distinct encrypted messages $Z$, all encrypted using the same $X$. This tells the eavesdropper nothing about $(X, Y)$, and therefore nothing about $Y$, because it's just a random subset of all $2^n$ possible $Z$ of length $n$. Thus, if my reasoning is correct, the strength of the encryption is limited only by $n$.

Given the existence of such provably hard problems, why do we rely on supposedly one-way functions that might turn out to not be hard? Like, say, factoring the product of a pair of large primes? Or, is its equivalent used in some form I do not recognize?

Note: Corrected to clarify that the original message is random, and that breaking it is not impossible but provably hard.

The flaw in your argument is the assumption that the original plaintext messages are random. Any real message must have some structure, otherwise the intended recipient has no way to interpret it. (If it's a compressed image, for example, there must be a file header to allow decompression.) If your message has any such structure in it, then the eavesdropper can use codebreaking tricks (like the XOR that Poncho suggested) to extract information.

If you have some way to (reversibly) turn a meaningful message into one that is indistinguishable from random noise, then that in itself is already a valid encryption method, and no additional step is necessary.

Even if an eavesdropper collects an arbitrarily large set of (distinct) encrypted messages, all generated using the same $X$, there will still be infinitely many degrees of freedom for $X$ and $Y$ conditional on that set.... Thus, if my reasoning is correct, the encryption is unbreakable.

Hold your horses; this is known to be incorrect.

What you propose (for two different values of $Y$) is known as 'two-time pad'; that is known to be breakable.

If the attacker has $m( X, Y )$ and $m( X, Y')$, he can exclusive-or those two together; what that is happens to be the same as $Y \oplus Y'$, that is, the exclusive-or of the two plaintexts. Now, for completely random unknown plaintexts, that doesn't tell the attacker that much (although it is quite sufficient to break the CPA assumption); on the other hand, plaintexts are often not completely random, but instead have a lot of structure, and the attacker can use that structure to recover the plaintexts. For example, if $Y, Y'$ are ASCII English plaintexts, then simple crib-dragging will recover the plaintexts with not that much work...

It turns out to be informationally secure, to protect $n$ bytes of plaintext, you have to use at least $n$ bytes of key (which can't be used for anything else). Hence, the reason we don't use these techniques is that transporting the key is generally infeasible (and often no easier than the 'transporting the plaintext' problem we are originally trying to solve). One of the ways of looking at cryptography is 'turning a long secret into a short secret' (e.g. by encrypting a long message with a shorter key); this is not what these 'informationally secure' methods do.

Your system cannot be more secure than a one-time pad (OTP) which has perfect secrecy. If analyzed [this is up to you to demonstrate security] it will most likely turn out to be less secure than an OTP. By the way, there are not infinitely many degrees of freedom for a system which is dependent on finite length strings, as you defined it.

There is one reason for not using a one-time pad, which has perfect secrecy, unlike yours, which is efficiency.

The transport of the key securely for a one time pad (key is as long as the message and the OTP is a symmetric cryptosystem) requires that a secure channel is already established and such a long key can be securely shared, which means the OTP is not needed.

In the normal setup, short symmetric keys (128 bits say) are shared using public key cryptography which are long term authenticated keys.