My question is: Does every hash value H have a value V?
For example, given md5 hash value f2c057ed1807c5e4227737e32cdb8669 (totally random), can we find what it was from?
These are actually two very different questions: whether there is an input for each output, and whether we can find an input for each output.
For your first question: we do not know. For a given hash function, the number of possible inputs is a lot bigger than the number of possible outputs, so we would find it very surprising if the function was not surjective (i.e. if there was an output without any matching input). For instance, with MD5, there are 2128 possible outputs, and 218446744073709551616-1 possible inputs, so we expect that each output has, on average, about 218446744073709551488 corresponding inputs. It is rather implausible that there is an output with no corresponding input.
However, we do not know how to prove it. To a large extent, we expect that property to be very hard to prove for any concrete hash function (such a proof of surjectivity would not, per se, be a weakness of the function, but, handwavingly, the security of a hash function relies on the intractability of its structure with regards to that kind of analysis).
For your second question: we strongly hope that it is infeasible. This is what is called preimage resistance: for a given output y, it should not be computationally feasible to find a x such that h(x) = y. Even if it was mathematically proven that such an input must exist (it is not proven, but it is strongly suspected, as explained above), it should still be atrociously expensive to actually find it.
If the hash function is "ideal" then the best possible attack is luck: you try out possible inputs until a match is found. If the output has size n bits, then "luck" should work with an average effort of 2n; with n large enough (and n = 128 is large enough), this is way out of what can be done with existing computers. A hash function is said to be resistant to preimages if "luck" is still the best known attack.
It is known that MD5 is not ideally resistant to preimages, because an attack with effort 2123.4 has been found -- about 10 times faster than 2128, but still a long way into the realm of infeasibility, so that attack is theoretical only.
I would like to point out two things, though:
If I give you h(x) for an unknown x, but you have some idea about the x that I used (e.g. you know that x is a "password" that a human user could choose and remember), then you can try possible x values that match that idea. The actual average effort for finding a preimage to h(x) is the smaller of 2n and M/2, where M is the size of the space of possible inputs x. For a "raw" preimage attack, all sequences of bits are possible inputs, so M is huge and the cost is 2n. However, if, in a specific context, x is known to be taken out of a relatively small space, then finding the "right" x can be substantially faster.
As pointed out above, preimages are not supposed to be unique: for a given y, a large number of values x should exist, that hash to y. Thus, for a given output, you do not find "the" corresponding input, but "a" corresponding input, which may or may not be the "right" one.
And the third question ? Indeed, trying to make a complete map of inputs-to-outputs is yet something different.
As @Xander pointed out, the number of possible MD5 outputs (2128) is too large to be stored anywhere on Earth; it exceeds the cumulated size of all hard disks that have ever been built. However, if you could solve that storage issue, then it is possible to think about the cost of making a complete map.
If you use the "luck" attack on all 128-bit outputs independently, you may expect an overall cost of 2256 (2128 times a cost of 2128). However, you can do much better by handling all outputs simultaneously, i.e. trying out random (or sequential) inputs and simply populating your big table as you obtain the outputs. With effort 2128, you should get about 63% of your complete map, while the "independent luck" method would need an effort of a bit more than 2255 to achieve the same result.
Edit: as was pointed out by @Owen and @kasperd, the arguments on the number of inputs are not actually sufficient to induce surjectivity; the internal function structure matters. MD5 and SHA-1 are Merkle–Damgård functions, meaning that they are built as follows:
There is an inner pseudorandom permutation P: for an input block b of a given size (512 bits in the case of MD5 and SHA-1), Pb is a permutation of the space of sequences of exactly n bits (n = 128 for MD5, n = 160 for SHA-1).
A compression function is defined, as:
f(b, x) = Pb(x) + x
That is, for block b, we apply the permutation corresponding to b on the second input x, and then we "add" x to the output of that permutation. (In the case of MD5 and SHA-1, that addition is done on a 32-bit word basis, but the details do not matter here.)
To process a complete input message m, the message is first padded with extra bits so that the total size becomes a multiple of the block size, and also encodes the original message length. The padded input is then split into successive blocks b0, b1, and so on. A register r is initialized to a conventional value of size n bits (the "IV", specified in the MD5 and SHA-1 standards). Blocks are then processed one by one: to inject block bi, we compute f(bi, r), and the output is the new value of r. When all blocks have been processed, r contains the complete hash function output.
The addition step in the compression function turns the pseudorandom permutation Pb into a pseudorandom function. A relevant consequence is that, for a given value b, f(b, x) is very unlikely to be surjective. In fact, we expect values f(b, x), for all 2n inputs x, to cover only about 63% of all possible 2n sequences of n bits.
This processing has interesting consequences. First, consider all inputs of size exactly 1 GB (the "traditional" gigabyte of exactly 1073741824 bytes): there are 28589934592 such sequences, i.e. a lot more than 2128. However, when applying MD5 on all these messages, they will all be padded with exactly one extra block (8589934592 = 16777216×512, so an extra block of size 512 will be appended), and, furthermore, this final block will be the same for all 1 GB inputs (it encodes the input length but is otherwise deterministic, with no randomness and no dependence on the values of the input bits). Let's call bz that final block. MD5 on a 1 GB input message m thus begins with a lot of processing on the first 16777216 blocks, resulting in a 128-bit value x, and the hash output MD5(m) is equal to f(bz, x).
Therefore, all 1 GB messages ultimately reduce to a single of the same compression function f(bz, x). Thus we expect the hash outputs to cover only about 63% of all 128-bit sequences. This example demonstrates that the argument on the number of inputs to the hash function is incomplete (though it gives the right idea).
Conversely, if we consider all messages of exactly 300 bits in length, then they will all be hashed as f(b, IV), with 2300 distinct blocks b. We thus have 2300 pseudorandom permutations Pb, all applied on the same 128-bit input (the IV), yielding 2300 128-bit results which are all, then, supposed to be uniformly distributed over the space of 128-bit values. Adding IV to all of them does not change that uniformity. In that case, the counting argument works and thus sujectivity becomes highly probable.
Edit 2: About the "63%". When you generate a random value, uniformly, in a space of size N, then the probability of hitting a given value x is 1/N; thus, the probability of not hitting a given value x is (N-1)/N.
Now try it N times: you generate N values randomly, uniformly and independently (in particular, you may generate several times the same value). For a given x, the probability of not being part of these N values is the probability of having been missed N times, i.e.:
P = ((N-1)/N)N.
This can be approximated as follows:
P = eN ln (1-1/N) = eN(-1/N + o(1)) = e-1+o(1)
Thus, with big values of N, the probability of any given value being missed approaches 1/e. Therefore, the expected coverage of the space of size N, with N random values, would be close to 1-(1/e). This is approximately 63.21%.