Steven Zahm@ Nico
re: However, I would like to first make a selection of a category and then the list of contact that have this category.
Well, you could, with any of the premium templates and then follow this tutorial on how to not display the directory until a category search is made.
Another option, you could use the [Enhanced Categories extension] and use the shortcode option if it adds to place the categories one one page and put the directory on another so when you click a category link you be taken to the page with the directory filtered by the selected category.
re: Is it possible to use an address as a widget?
Well, technically possible but there is not one available. Question. Do you mean to put a directory entry with their address in the sidebar OR when you visit the directory entry’s profile page have the entry’s address shown in the sidebar using a widget?
re: Can contacts be somehow integrated into the search?
Sorry, no, it is not possible is integrate with the core WP search. It is specifically code to search the site’s pages and posts and there is no way to hook into it to do custom searches which are required to search the directory.
Hope that helps!