After hours of desperation and hundreds of trials & errors, I've come up with the solution below.

I had the same issue, when I wanted just one xmlns attribute, on the root node only. But I also had a very difficult query with lot's of subqueries and FOR XML EXPLICIT method alone was just too cumbersome. So yes, I wanted the convenience of FOR XML PATH in the subqueries and also to set my own xmlns.

I kindly borrowed the code of 8kb's answer, because it was so nice. I tweaked it a bit for better understanding. Here is the code:

DECLARE @Order TABLE (OrderID INT, OrderDate DATETIME)    
DECLARE @OrderDetail TABLE (OrderID INT, ItemID VARCHAR(1), Name VARCHAR(50), Qty INT)    
INSERT @Order VALUES (1, '2010-01-01'), (2, '2010-01-02')    
INSERT @OrderDetail VALUES (1, 'A', 'Drink',  5),
                           (1, 'B', 'Cup',    2),
                           (2, 'A', 'Drink',  2),
                           (2, 'C', 'Straw',  1),
                           (2, 'D', 'Napkin', 1)

-- Your ordinary FOR XML PATH query
DECLARE @xml XML = (SELECT OrderID AS "@OrderID",
                        (SELECT ItemID AS "@ItemID", 
                                Name AS "data()" 
                         FROM @OrderDetail 
                         WHERE OrderID = o.OrderID 
                         FOR XML PATH ('Item'), TYPE)
                    FROM @Order o 
                    FOR XML PATH ('Order'), ROOT('dummyTag'), TYPE)

-- Magic happens here!       
SELECT 1 AS Tag
      ,NULL AS Parent
      ,@xml AS [xml!1!!xmltext]
      ,'http://test.com/order' AS [xml!1!xmlns]
FOR XML EXPLICIT

Result:

<xml xmlns="http://test.com/order">
  <Order OrderID="1">
    <Item ItemID="A">Drink</Item>
    <Item ItemID="B">Cup</Item>
  </Order>
  <Order OrderID="2">
    <Item ItemID="A">Drink</Item>
    <Item ItemID="C">Straw</Item>
    <Item ItemID="D">Napkin</Item>
  </Order>
</xml>

If you selected @xml alone, you would see that it contains root node dummyTag. We don't need it, so we remove it by using directive xmltext in FOR XML EXPLICIT query:

,@xml AS [xml!1!!xmltext]

Although the explanation in MSDN sounds more sophisticated, but practically it tells the parser to select the contents of XML root node.

Not sure how fast the query is, yet currently I am relaxing and drinking Scotch like a gent while peacefully looking at the code...

It would be really nice if FOR XML PATH actually worked more cleanly. Reworking your original example with @table variables:

declare @t1 table (c1 int, c2 varchar(50));
declare @t2 table (c1 int, c2 int, c3 varchar(50));
insert @t1 values 
    (1, 'Mouse'),
    (2, 'Chicken'),
    (3, 'Snake');
insert @t2 values
    (1, 1, 'Front Right'),
    (2, 1, 'Front Left'),
    (3, 1, 'Back Right'),
    (4, 1, 'Back Left'),
    (5, 2, 'Right'),
    (6, 2, 'Left');

;with xmlnamespaces( default 'uri:animal')
select  a.c2 as "@species",
    (
        select  l.c3 as "text()"
        from    @t2 l
        where   l.c2 = a.c1
        for xml path('leg'), type
    ) as "legs"
from @t1 a
for xml path('animal'), root('zoo');

Yields the problem XML with repeated namespace declarations:

<zoo xmlns="uri:animal">
  <animal species="Mouse">
    <legs>
      <leg xmlns="uri:animal">Front Right</leg>
      <leg xmlns="uri:animal">Front Left</leg>
      <leg xmlns="uri:animal">Back Right</leg>
      <leg xmlns="uri:animal">Back Left</leg>
    </legs>
  </animal>
  <animal species="Chicken">
    <legs>
      <leg xmlns="uri:animal">Right</leg>
      <leg xmlns="uri:animal">Left</leg>
    </legs>
  </animal>
  <animal species="Snake" />
</zoo>

You can migrate elements between namespaces using XQuery with wildcard namespace matching (that is, *:elementName), as below, but it can be quite cumbersome for complex XML:

;with xmlnamespaces( default 'http://tempuri.org/this/namespace/is/meaningless' )
select (
    select  a.c2 as "@species",
        (
            select  l.c3 as "text()"
            from    @t2 l
            where   l.c2 = a.c1
            for xml path('leg'), type
        ) as "legs"
    from @t1 a
    for xml path('animal'), root('zoo'), type
).query('declare default element namespace "uri:animal";
<zoo>
{ for $a in *:zoo/*:animal return
    <animal>
    {attribute species {$a/@species}}
    { for $l in $a/*:legs return
        <legs>
        { for $m in $l/*:leg return
            <leg>{ $m/text() }</leg>
        }</legs>
    }</animal>
}</zoo>');

Which yields your desired result:

<zoo xmlns="uri:animal">
  <animal species="Mouse">
    <legs>
      <leg>Front Right</leg>
      <leg>Front Left</leg>
      <leg>Back Right</leg>
      <leg>Back Left</leg>
    </legs>
  </animal>
  <animal species="Chicken">
    <legs>
      <leg>Right</leg>
      <leg>Left</leg>
    </legs>
  </animal>
  <animal species="Snake" />
</zoo>