Could a Van Emde Boas tree be used for storing matrices?
Yes you are right; but actually I think what you need is a hash table, which supports insert, delete and find in O(1) (although it requires some randomization).

Of course, you can replace a hash table by a VEB tree, when the elements are integers. However, if you want to optimize the space usage, you still need hashing when constructing the VEB tree. Luckily, there's some data structure called Y-fast trie that supports operations similar to VEB tree, but only needs linear space, and is deterministic.