Resolving CNAMEs when pointing to another domain

[G. Del Merritt]

I see a bunch of CNAME questions in the archives, but none recently with 
quite the problem I am having.  If there is a better list to look at for 
resolver issues, please point it out to me in private email.

I am working with a third party vendor.  We want to provide a "uniform" 
service, so my vendor says to set up records like this:
      foo.mydomain.com IN CNAME foo.mydomain.com.theirdomain.com

They will in turn handle the A record for foo.mydomain.com.theirdomain.com, 
since over time they may choose to move the service to some other box under 
their control.

The problem is that if I just point my browser (IE, Netscape, Lynx - 
doesn't matter) at "foo.mydomain.com" I get a lookup failure.  However, if 
I do the following:
    # nslookup
    > lserver myispDNShere
    > set type=any
    > foo.mydomain.com
    foo.mydomain.com   canonical name = foo.mydomain.com.theirdomain.com

Then I point my browser at "foo.mydomain.com" and, voila!, it "works".  It 
continues to work for about an hour (which happens to be the TTL on the 
CNAME record) and thereafter it fails to resolve until I again do an 
nslookup for "my" name.

It doesn't appear to matter whether my client resolver is running on 
Windoze or Linux; I see the same behavior for both.  And it doesn't seem to 
matter whether my client's nameserver is pointing at a Windoze or a Linux 
box.  So it appears that I am somehow running afoul of "correct" behavior, 
but I don't understand why.  My guess is that the resolver is saying:
    OK, give me an A record.
    Drat; didn't get that.
    Got a CNAME?
    Yeah, got that; I guess I'm done.

Except that I guess somehow it's "working" when I use nslookup to fill in 
the nameservers cache, so the dialog may go more like this:
    OK, give me an A record.
    Drat; didn't get that.
    Got a CNAME?
    Yeah, got that; oh, and I see you've told me what the CNAME points to!

Your suggestions welcome.  I have complete control of my nameservers.  In 
fact, they are running a variant of lbnamed so that I can fabricate these 
names on the fly.  An artifact of lbnamed is that it doesn't do 
recursion.  Is that likely to be my problem?  If so, why?

--
G. Del Merritt                                dmerritt at intranets.com
http://www.intranets.com - Get everyone on the same page(sm)