[Manishearth, I'm not sure I'm even answering the right question below. After reading your question more carefully, I think you were more interested in how water molecules help crystals form, rather than whether or not the anhydrous forms can form crystals also (versus being strictly amorphous). So, oops. Maybe some one else has a good answer on the water molecules part?]
I suspect the answer is an issue of process rather than of fundamentals.
That is, if you could find a non-aqueous medium that readily dissolves the anhydrous form of some salt, my very strong suspicion is that you could grow excellent clear crystals of it that would look almost nothing like the hydrous crystalline forms.
The problem for metallic-anion salts in particular is that finding a liquid that dissolves the salt without simultaneously forming strong coordination complexes with it is going to be tricky, since I'm guessing it's usually the coordination effect that help ionize the units of the material to make it soluble!
Here's a wild guess: Someone, somewhere, has likely done research on how to grow crystals of substances such as anhydrous $\ce{CaSO4}$ (hmm, why does this phrase "dead burnt plaster" come to mind? :) or anhydrous $\ce{CuSO4}$ by using low-temperature molten solutions of... something or other? Not sure what!
And what a delightful crystal that would be to have! It would be way out of the ordinary despite being so very... ordinary?... in one sense in its composition.
Update: Apparently, clear crystals of anhydrous $\ce{CuSO4}$ do indeed exist, and are easier to create than I thought. You just add concentrated sulfuric acid [a] to ordinary copper sulphate pentahydrate solution and let it evaporate slowly. Since $\ce{H2SO4}$ is one of the most aggressive drying agents in existence, my guess is that the $\ce{CuSO4}$ just can't compete for the remaining water molecules and is forced to crystallize without hydration.
[a] Please, never ever attempt to use concentrated $\ce{H2SO4}$anywhere except in a real lab with protections and procedures fully in place. This is a compound that wants water so badly that it willy synthesize water right out of the hydrogen and oxygen bonded into proteins and carbohydrates, leaving only charred carbon. Ironically, the actual acidity of concentrated (vs hydrated) $\ce{H2SO4}$ is quite moderate, comparable to that of vinegar.
Addenda:
-- Another common-exotic crystal may be lithium fluoride, $\ce{LiF}$, although the accuracy of that seems to depend on who you read. Unique how, you say? Even though lithium was an early result of the Big Bang, lithium and fluorine are both consumed rapidly by large hot stars, especially fluorine. Their existence on earth thus appears to depend on processes such as proton irradiation and possibly even intensive neutrino irradiation tht only occur during the explosion of a supernova star, rather than being inherited from before the cataclysmic event. Pretty much all of the elements (except $\ce{H}$) here on Earth are star-forged of course, but the elements in $\ce{LiF}$ crystals thus may be remnants of the supernova event itself. That would... cool!)
-- And speaking of unique, wearable crystals: I've always wondered if there's a market out there for diamond crystals synthesized using carbon that was captured as carbon dioxide during the cremation of a loved one. If there is, feel free -- that is definitely not my bailiwick!