Deep mind just released a couple of papers about this:
https://deepmind.com/blog/neural-approach-relational-reasoni...
Here is an implementation of "A simple neural network module for relational reasoning" in pytorch: https://github.com/kimhc6028/relational-networks
What you describe is very similar to the concept of Differentiable Neural Computer, from DeepMind [1]. While still experimental they already have nice results.
[1] https://deepmind.com/blog/differentiable-neural-computers/
I'd put a little more faith in LSTMs. There's a lot less evidence for what they can't do than what they can. With enough fiddling, can get LSTMs to work for most tasks.
I'm not sure they're quite as complicated as you're making them out to be. If they are, then try a GRU instead ;)
Any links to implementations?
Yes, one of the links is from DeepMind: "A simple neural network module for relational reasoning" https://arxiv.org/abs/1706.01427
Another one is from Thomas Kipf: "Graph Convolutional Matrix Completion" https://arxiv.org/abs/1706.02263
That's because it doesn't factorize the input into separate meaningful parts. The next step in LSTMs will be to operate over relational graphs so they only have to learn function and not structure at the same time. That way they will be able to generalize more between different situations and be much more useful.
Graphs can be represented as adjacency matrices and data as vectors. By multiplying vector with matrix, you can do graph computation. Recurring graph computations are a lot like LSTMs. That's why I think LSTMs are going to become more invariant to permutation and object composition in the future, by using graph data representation instead of flat euclidean vectors, and typed data instead of untyped data. So they are going to become strongly typed, graph RNNs. With such toys we can do visual and text based reasoning, and physical simulation.