Must Neural Networks always converge?
(I assume by "error propagation" you mean what I call "error back-propagation.")

On page 231 of Neural Networks (by Haykin), he states that back propagation always converges, although the rate can be (in his words) "excruciatingly slow."

I think what you are asking though is not whether the algorithm will always converge, but whether it will always converge to the optimal answer. And unfortunately, it won't. Even in simple cases like yours, it's entirely possible that there are local minima which are not global minima.

Dealing with local extrema is a hugely important topic in optimization, and you can find a plethora of advice on how to deal with it. One of the most common is what it sounds like you're doing: random restarts (i.e. just run the algorithm multiple times, each starting from a random place). 

To figure out if there's a bug in your code, I would print out the error term and verify that it decreases at each iteration. If so, then you're probably just hitting a local minima.