Well, there are a few logal rules that apply.
Most importantly, you can't link what's not there.
So John cannot work for '123 enterprises' unless '123 enterprises' exists.
That means your web-interface can never offer you the choice of linking John to 123, because there is no 123.
The same applies for John himself, you can't link him if he's no there.
So you don't have to check wether John or 123 exist, because if they don't, there's no way to get John to work for 123 in the first place.
If you're loading the data from a textfile or something, the 'obviously' you'd have to load the companies first, then the people, and then build the relations between them.
PS: make sure you either use MySQL with InnoDB, or no MySQL at all. MySQL without InnoDB does not support PK/FK constraints, which means you can link John to 123, and then remove 123 without problems, which is ofcourse extremely unbelievably bad.
A forum, a FAQ, what else do you need?