Additional Customer Fields, Multiple Admin Emails and Authorisation

Ability to create additional user fields (I believe it already does this). Such as a Fax, Company details and multiple categories?

For user registration you mean? Yes. You can collect this information and make it part of

When a user goes to the registration page they have more details they need to provide?

Not sure what you mean exactly. Normally you capture all their details in the registration form. There is no registration page, really, unless you mean the page where the form is embedded. In that case, there is just one form: your registration form.

Once they register, an email needs to go to several email addresses (not just the site admin). is this possible?

You, you can send the notification to multiple email addresses as CC or BCC

Once approved, the user can login (I think this needs another plugin but thought I'd see if yours does this)

User moderation (the ability to 'approve' a user) is a feature of the 1.5beta release of the User Registration add-on, not any earlier version. Once you approve them, they can log in immediately. If they are not approved, they cannot log in. If you don't want to moderate them, they can log in immediately after they register.

A user can then edit all registration fields including the newly created ones?

Again, there is no separation of newly created fields or originally created fields. All the information would normally be captured in one form.

Updating that information is a feature of the 1.5beta release of the User Registration add-on as well, but not prior versions.

I can search all fields and can query this info in custom loops? I ask this as I'm trying to create a member directory so need to see all in category X or who's company name starts with Y

Search is handled by WordPress, not Gravity Forms. Gravity Forms collects the data for you. Searching through your users would not be handled by Gravity Forms, although it can certainly be done with WordPress.

The User Registration add-on is available with a Gravity Forms Developer license.

The User Registration beta is available for download here: http://www.gravityhelp.com/downloads/add-ons/#User_Registration_Beta

I'm not sure what WordPress plugin would be best for searching user profiles. I suspect that the WordPress built in search would not find any data stored in your user profiles. So, you may need some other approach to make this information searchable on your site.

You can pull whatever data you want out of your database. Can you explain exactly what information you want to pull out and display on a page? With more information we can help you with more specific support.

If you want the user to be able to edit this information, I think I would make it part of their user profile. You can capture all the information in the form, and it would be stored in the database, but if you don't extend the user profile to show the information, no one would know it was there, and there would be no way to edit it either.

You can learn more out about extending the user profile here:
http://justintadlock.com/archives/2009/09/10/adding-and-using-custom-user-profile-fields

There are other tutorials as well, but basically, Gravity Forms will capture the information, and then it's up to you to use it where you want.

What you want to do can be done, but it will require some work. The post by Justin Tadlock explains in great detail how to accomplish it. I think I understand what you're trying to do, and it can be done. The search issue still needs to be resolved; some sort of plugin to search user profiles.