It's very easy  to connect  records.

You probably will want to start by creating a custom list  called
Companies. If you need to be able to link  companies to companies
(presumably linking a company  to its parent company), I would add a
column called "Parent Company" and make it a lookup column, telling
it to get the lookup information from the Company column (or
whatever you called it) of this same list.

For starters, add a few companies for testing purposes.

Then create a contacts  list, and add a lookup column
called "Company", telling it to get the lookup information from the
Company field of the Companies list.

This should allow companies to be linked  in groups (one parent with
any number of children), and any number of contacts for each company.

If contacts need to be linked to Users, add a lookup column that
points to the User Information table.

To represent the data  in a tree  structure, you'll want to create one
or more views that use the Grouping facility. You could group all
your contacts by company, for instance. If you want to group your
contacts first by parent company, you will probably need to add
a "parent company" lookup field to the Contacts list.

We're using a lot of inter-related lists  like this and they work
well. If you want to work within the sharepoint  UI, you occasionally
need a bit of redundancy like the extra parent company field above,
but they go together in minutes and work rather effectively.

The relationship between companies and contacts  is many-to-many. One
company can have many contacts and one contact  can belong to several
companies. In a regular database  design you would add a link  table to
solve this. How would you solve this in SharePoint?

Another issue I see arising is the synchronisation with Outlook. I know
this is a one way street (SPS to Oulook), but from your explanation I
understand you'd use several lists  to store  the company  and contact
data. Would you sync the contact list  only then?

I assume you are talking about contact lists with added fields. Or are
you talking about real custom  lists?

I'll check out the grouping for the tree  view.

I have to create a list  presentation that is, as far as I know, not
possible with the standard list template  options.
- I need to represent a tree  structure that has grouping greater than 2
levels.
- I need to be able to list the same record in several locations in this
tree (same contact  linked to several companies). I do not know
beforehand how many links need to be made.

Can a custom  template be built in VS.Net to create this representation?
The standard templating options are certainly not sufficient.