Custom handling of domain user profile creation
Solution 1:
What you could do in this case, is to create a windows service running with LocalSystem privileges and communicate with it with your credentials provider.
When a user enters his/her credentials to the ICredentialsProvider, the would contact the windows service and the service will handle the authentication.
Upon a successful authentication, the service should verify that such an account is locally present in the system otherwise create a new local account with NetUserAdd and log in with that account into the system.
Bear in mind that ICredentialsProvider does not have the privileges to create local account or use most of the Net* functions, that's why I'm suggesting to create a windows service with LocalSystem privs.
Solution 2:
If you just want to make a small number of changes to profiles then you might consider using Active Setup.
Once you set this up on the machine it will run just after the user's profile loads, and you can then make user-specific changes to their files/settings etc.