Microsoft's recommendation is 2000 users per BDC. 10000 is about the MS limit for the number of users/machines/groups (40mb SAM) that MS will say can be safely supported. Of course you can go beyond those recommendations but then you go into uncharted territory. =)
With a P3/500 you should have no problem servicing that many people. Make sure that your BDCs and PDC are configured logically and physically so people don't have to go over WAN links (typically slower). If you have a larger concentration of personnel at one facility than another maybe make sure that they have there own dedicated BDC. But, rule of thumb is that every sat. office (WAN link) has a BDC and that your main office have a BDC and PDC. That should allow you tohave fast authentications and redundency in case of failure.
Authentication is based upon the browser. When a machine boots up it announces itself to the master browser of its segment. Now, the segment is a cluster of 32 machines, not neccessarily physically close to one another. So, if 1 machine from LAN2 announces itself as a BDC and 31 machines announce themselves on LAN1 than the 31 machines of LAN1 will authenticate on LAN2.
Use WINS and use it correctly. Also, adjust your workstation/DCs browser settings to compensate.
GL