This seems to get closed to the required output:

Updated: Corrected fencepost-ish error.

Update2: Added a second pass to condense it a bit.

#! perl -slw
use strict;

( my $input = do{ local $/; <DATA> } ) =~ tr[\n][]d;

my $tab = 0;
$input =~ s[([()])]{
    $tab-- if $1 eq ')';
    my $modified = "\n" . ( "    " x $tab ) . $1;
    $tab++ if $1 eq '(';
    $modified;
}ge;
$input =~ s[\n\s+\)][)]g;

print $input;

__DATA__
(&(&(&(& (mailnickname=*) (| (&(objectCategory=person)(objectClass=use
+r)(!(homeM
DB=*))(!(msExchHomeServerName=*)))(&(objectCategory=person)(objectClas
+s=user)(|
(homeMDB=*)(msExchHomeServerName=*)))(&(objectCategory=person)(objectC
+lass=cont
act))(objectCategory=group)(objectCategory=publicFolder)(objectCategor
+y=msExchD
ynamicDistributionList) )))(objectCategory=contact)(proxyAddresses=smt
+p:*exampl
e.com)))
[download]

Yields:

P:\test>junk1

(&
    (&
        (&
            (&
                (mailnickname=*)
                (|
                    (&
                        (objectCategory=person)
                        (objectClass=user)
                        (!
                            (homeMDB=*))
                        (!
                            (msExchHomeServerName=*)))
                    (&
                        (objectCategory=person)
                        (objectClass=user)
                        (|
                            (homeMDB=*)
                            (msExchHomeServerName=*)))
                    (&
                        (objectCategory=person)
                        (objectClass=contact))
                    (objectCategory=group)
                    (objectCategory=publicFolder)
                    (objectCategory=msExchDynamicDistributionList) )))
        (objectCategory=contact)
        (proxyAddresses=smtp:*example.com))
)
[download]