Mathematical Problem Solving
Will a study of the mathematical proof of a problem [..], highlight peculiar properties of the problem which may help in designing an optimal algorithm?


Often they do. But not necessarily (unless you're a scholar of constructivism), for example when using the probabilistic method to show that a solution to said problem exists, then the proof will not help you designing any algorithm since it does not give you a construction.


  Since the program is expected to return a true response for every input, proof must be, in some way, built into the program.


That would be nice if it were the case, but often proving correctness (see formal methods) of an algorithm is rather difficult and/or a real pain. That said, there is such a thing as proof-carrying code which does exactly that, but the proofs are not given to you for free.