Genetic Algorithms: Converge to best solution for one, few or many environments?
Unless you define "wide variety" very precisely and prove that your algorithm is able to abstract over all varieties in the way you want, then yes, you'll have to test it every time. I think for most interesting problems you won't be able to produce such a proof. 

For a related entertaining read, check Neural Network Follies. The author describes a project where a neural network was trained to spot tanks in images. Instead the network learned how to tell whether it's sunny or not.