Are there solutes that are insoluble in water?
Yes, normally we call them bricks.
Materials that are non-molecular are generally insoluble in any solvent. This includes ionic species (especially those with ions of mulitple charge, phosphates, carbonates, oxides, sulfides), and also network covalent solids such as glass (and bricks) and carbon. Water is an exceptionally powerful solvent, because it can solvate (i.e. dissolve) a variety of ionic solids.