This is a little tricky with Multi-Texture but not impossible. The problem is that the multi-sub material loops through the IDs when they're out of range on the source geometry. So for example with a multi-sub where ID1 = grout and ID2 = brick textures(with multitexture map), if the face id is 3,5,7,8 ... you will get the grout texture instead of the brick texture.
The solution therefore is to make sure that the multi-sub texture's number of IDs is the same as the randomisation range of the material operator. So imagine you have 9 brick textures. You would need to create a Mult-Sub material with the Grout in ID1 and the Bricks material instanced into ID slots 2-10.
You can then set the Material operator up to randomise within that range:
You might also be interested to know that VizPark's Crossmap
plugin does not suffer from this limitation as it can randomise by V-Ray instances, so doesn't need randomised IDs. In my tests, it worked well for situations like this.
I hope that helps, please let me know if there's anything else I can do.