As stated in the last edit of my question, the issue indeed was to do with the softmax function.

As clarified [here][1] We shouldn't apply softmax directly to the result of the last LSTM. Notice, LSTM will produce a vector of values, each of which is bounded between -1 and 1 (due to the tanh squashing function that's applied to the Cell).

Instead, I've created a traditional fully-connected layer (just additional weight matrix), and feed result of LSTM to that layer. This "output" layer isn't activated - it feeds into a softmax function, which actually serves as an activation instead.


I modified  the back-prop algorithm to supply the gradient generated by the softmax to the Output layer. Of course, if you used a cross entropy Cost function originally, then such a gradient will remain $(predicted - expected)$. It's then pushed through the weights of that Output Layer, to get the gradient w.r.t. LSTM. After this the backprop is applied as usual and the network finally converges. 


**Edit:** I noticed the momentum was computed incorrectly.

> Also, using a momentum coefficient with 0.2; It's applied to the previous frame's gradient. I don't increase momentum while the program executes, but keep it at a constant 0.2;

    newgradient = newgradientMatrix + prevFrameGradientMatrix*0.2

That's incorrect, - instead it should be 

    newgradient = newgradientMatrix*(1-0.9) + prevFrameGradientMatrix*0.9

Which is an exponential moving average, that remembers roughly $\frac{1}{0.1} = 10$ days. 

On the 10th day, the coefficinet will be $$\frac{(1-\epsilon)^{\frac{1}{\epsilon}}}{0.9} = \frac{(1-0.1)^\frac{1}{0.1}}{0.9} = \frac{0.9^{10}}{0.9} \approx 0.387 \approx \frac{1}{e}$$ of the peak; Because 9 newer days have larger coefficients (larger than 0.387), their avearge really makes 10th day and older be negligible

Any older days will have even less contribution

Also, don't forget about the bias correction, - which helps get a better estimate when we are 'just starting' to compute the average. Without the bias correction it would start very low, and will take some time to catch-up with the expected 'exponential moving average'

    newval = curval*(1-0.9) + prevVal*0.9
    newval /= 1-(0.9)^t  //where t is timestep

However, I don't know if bias correction is applicable to momentum

  [1]: https://datascience.stackexchange.com/questions/25531/softmax-classifier-never-allows-for-100-probability-in-lstm