You could use a separate NAB and add it via Domino's Directory Assistance to the server.
This allows you to create the external users from the other company in this NAB only and won't affect your companies names.nsf.
The external users would have their own company hierarchy, something like
*/Acme/US
f.e.
Mary Jane/Acme/US
The can login with the default Domino mechanism (including the password change mechanism etc). And you can use the other features of Domino like Groups, ACLs etc.
The users would log on to your site with their email adress, that's why there is no be problems with "doubled users" (Hans Mueller/Acme/US and Hans Mueller/YourCompany/US).
The DA must only run on the Webserver that the external users should access. You don't have to replicate it all around in your infrastructure.
EDIT:
You can create user documents in this external NAB without any problems. I prefer a self-registration with a email validation mechanism (to prevent the use of an internal email adress, f.e. of [email protected]).
The users can choose their own password. All you have to do is to create a new Person document in the NAB and do a Compute with Form (this sets the HTTP password).
If a user wants to change the password, you can use the ?ChangePassword functionality. And if a user forgets his password, an agent creates a new one in the person document and sends it via mail to the user email address.