Shape ID is 32 bit ("long", in VBA terms)
The limitation of 2-byte array applies only to the SetFormulas/GetFormulas functions, probably for historical reasons.
Anyways, Visio will sure be dead long before you actually try to put 64.000 shapes on a diagram, so I would not worry about that much.
A huge number of details while keeping number of shapes/recalculations low is usually achieved by using vector-style-images (wmf, emf, svg) as shapes.
This is done by most equipment stencil providers, like CISCO, HP, etc.
This approach allows you to have basic operations like move/resize (as a group), while not consuming costly computational resources for formulas.
Basically, usually you don't really need "smartness" for every single detail shape (except for basic move/resize), you need "smartness" only at the "top" level.