Solutions, solvents and solutes
When you make assumption for guessing the solubility of the molecule in some solvent you should consider the whole molecule, his structure and his size.

We can start with the ether, in the below figure (from wikipedia the one at right ) is shown a diethylether molecule.
                           
You can see that is quite a non-polar molecule (charge 0,green, in the most part of the surface) so this explains why has a low solubility in a polar solvent like water. Same thing for Vitamin A:
                           
The most part of the molecule is not polar. Only one $-OH$ can't make the difference. And so is for 1-Octadecanol that has a solubility in water of $1.1  \times 10^{-3} mg/L$ and Nonadecyl alcohol (1-nonadecanol) seems something like $4.8  \times 10^{-3} mg/L$ both up to my references have very low solubility in water (where did you find that were not?). For the $CO2$ is true what you have stated it has not a very strong polarity (but in fact it has a little bit!) because is a linear molecule.
                                       
This last example let me introduce to an important factor that influence the solubility: molecule size.
Little molecule are more easily solvatated by solvent molecule, this bring us to the case of cellulose:
                  
Cellulose is very hydrophilic and so should be soluble in water, but this doesn't happen because cellulose is a polymer (in figure is show his monomer) that can have a molecular weight very hight. Polymers may swell but can't be solubilize if their chains are bonded with chemicals bonds until the bonds are break.