Haemoglobin does solve this difficulty, of course - it has to! But how?
The first thing to understand is that the problem isn't quite as bad as it seems. The amount of oxygen bound to haemoglobin depends on the concentration of oxygen in the blood at any time. In other words, the equation looks something like this:
Does that solve the problem? Well, it does allow for a passable form of an oxygen transport protein, but it would still clearly be much better if its affinity for oxygen could change, wouldn't it? Otherwise, we would have either a protein that was great at taking oxygen from the air, but awful at releasing it to the tissues, or else a protein that was incredibly resistant to binding the oxygen in the lungs, leading to a situation (similar to when we didn't have an oxygen transport protein) of relying mostly on dissolved oxygen reaching the tissues. We've have already identified the latter option as being physiologically disastrous.
Alas, there is one more problem to be solved. Just how is haemoglobin supposed to signal to the other haemoglobins to change their affinities? Each molecule is an isolated individual, and communication between them would require complicated machinery on each.
As ever, the solution is more elegant. Haemoglobin is really a tetramer consisting of four subunits. Each subunit consists of a haem group surrounded by the globin protein, in a structure mentioned in Part 1. It's just that this motif is repeated four times in each haemoglobin molecule. (Diagram below - subunits in blue and red, with the haem parts in green...)
Oh, one last thing? Why package the haemoglobin molecules into a cell (the well-named red blood cells)? Not all animals do so; some simply have it floating freely in the plasma. But in these cases "about 3 percent leaks through the capillary membrane into the tissue spaces or through the glomerular membrane of the kidney into the glomerular filtrate every time the blood passes through the capillaries." (Textbook of Medical Physiology, 10th Edn. Guyton and Hall)