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. 



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