As I was in a hurry to deploy a development environment for CRM 4.0 I chose to deploy MS CRM 4 in English (base language) and then I applied and enabled the Portuguese Language Pack (at server level). Just for testing purposes I went to Tools and changed the language to Portuguese. The page refreshed and in no time I was working with my MS CRM 4 in Portuguese. However I must warn you that some administration features are only available in the base language.
Afterwards I installed the Outlook client for CRM (EN) and after I configured it properly I opened Outlook (PT) again and with great joy I realized that the Outlook plugin was working in my Outlook language (PT). Just like magic! I didn't have to install any language pack on the client side! It's incredible when things work the way they're supposed to! Two or three buttons were in english but that's not a problem for me!