Does freezing a solution with water always cause the water to separate and form the ice lattice?
The purification that occurs when an aqueous solution freezes is called Fractional Freezing and is based on the idea that impurities of a solvent (and this can be any solvent, not just water) have a much lower solubility in the solid phase of the solvent relative to the liquid phase.   Several techniques for performing fractional freezing for purification purposes can be found here.   As the solid is formed, the impurities are expelled into the liquid that hasn't yet solidified.  The purified crystals can then be removed by physical methods (e.g. filtration).  In the case of water, where ice is less dense than the liquid phase, the purified crystals float to the top of the impurity-laden liquid.  This is probably the reason why some people have observed a layer of impurities deep within a block of ice.  As mentioned above, the process is not limited to just water, and freeze crystallization is use to eliminate the purities of silicon wafers and has been known for many years as a way to make hard liquor.  This latter use of fractional freezing is close to the OPs question, which inquires about miscible substances (in this case, ethanol and water).  Despite their miscibility, ethanol and water can be separated by fractional freezing, just like they can be separated by fractional distillation.  Certain substances cannot be separated completely using distillation, and these substances are called azeotropes.  Water and ethanol make an azeotropic mixture that is approximately 95% water.  (So the moonshine you were thinking of making using the reference above will be limited to 190 proof.)  What I find interesting is the following figure, 



which shows the freezing point of water/ethanol mixtures as a function of ethanol content.  At a point around 95% there is a significant dip in the freezing point.  At this point, called the eutectic point, the solution behaves as if it is a single component (much like an azeotrope) and will not likely be separable through 'simple' fractional freezing means.  Note I use the term simple because azeotropes can be separated using special distillation techniques.

So in summary: fractional freezing will work with any aqueous solution, regardless of the miscibility of the components, unless the component ratio is close the eutectic point.  We don't need to limit ourselves to aqueous solutions, as many species can be purified in this manner.  The purification mechanism is not so much a factor of the crystal lattice, but the relative solute solubilities in the solid and liquid phases of the solvent.  Finally, many water solutions will freeze solid even with impurities.  This and other types of separations work on equilibrium processes, and multiple iterations are necessary to "completely" remove impurities.  (or more correct, remove the impurities to a level that is acceptable for your application.)