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:** There is slight improvement to momentum.

> 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 fine, but changing the momentum-coefficient will require us to also re-adjust learning rate. A cleaner version will 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, in practice, it will be fine after approximately 10 timesteps - and so there is no real need for the bias correction in Momentum, but it should be done if we are using combination of Adam (a combination of Momentum & RMSProp)
  [1]: https://datascience.stackexchange.com/questions/25531/softmax-classifier-never-allows-for-100-probability-in-lstm