Hi,
unfortunately I was not able to find the problem yet.
I have also tested my network on the MNIST image classification dataset, where it would train properly as well even for larger batch sizes.
The difference is that all images in this dataset are of the same size, so no padding is needed.
Now I know at least that the bug is either in my sequence padding function (although I debugged it and everything seemed fine) or how the RNN handles the padded sequences.
Let me know if you encounter a solution to the problem or get an RNN with padded sequences to work!