The divisible by 16 rule isn't an arbitrary choice made by player manufacturers, it's due to the codecs involved. More specifically, it is because the codecs use discrete cosine transformations for spacial compression. Because color channels are subsampled at 4:2:0, their 8x8 blocks actually represent 16x16 areas in the image. So, you get 16x16 macroblocks.

MPEG-4 Part 10 supports other block sizes, if I recall correctly, but I don't know that they provide the same compression efficiency.