As of now, to get random movement of my enemies, I am adding a Rigidbody and a BoxCollider then "throwing" them (i.e. adding velocity) in a random direction for a random amount of time and making them choose a new direction if ever they get outside of their designated area. This does not seem to work that well all the time. Sometimes they manage to get themselves stuck inside obstacles which should be impossible. The more I add guys, the more it seems the physics can't keep up or something with the collisions. Is there a better method to random movement or is "throwing" them perfectly valid? Is my method expensive and terrible? I might have around 50 guys active at a time and perhaps a few hundred to a thousand static obstacles each with their own colliders.
Throwing them is perfectly valid and it is not a bad way of doing things unless you find that it becomes an issue. The amount of collisions you are describing should not be too expensive unless your Colliders are complex and you are running on a platform that has limited resources.
The "getting stuck" part is the bigger concern. There are a number of reasons that could be happening. You might can avoid this by changing the collision detection on the objects'
rigidBody to Continuous instead of discrete. You normally wouldn't want to do that unless the objects are moving extremely fast because continuous does have a higher CPU cost.
You can build a Navigation Mesh of your movable area and send your agents to arbitrary positions inside its bounds.