Fascinating, I had no idea this was so widespread. Always thought of nautilus as a forgotten species, nobody cared much about them except science. I'm envisioning this all wrong I guess, these sound like pretty steep dropoffs (300m, 500m) but they are still associated with the reef? Where does the reef "end"? I need to find myself some ROV footage!
As for captive specimens, we always fed them dead shrimp, squid or large krill. They seemed to love that large krill, which is why I always thought of them as a midwater type of animal. I also remember feeding them live pinead shrimp, but maybe those were skewered prior to feeding. Midwater animals aren't always "fast" :-) (jellies&other drifters) And as for reproduction in captivity, I believe only Waikiki Aquarium and maybe an aquarium in Japan has had success with that. Pretty sure the animals we used to have here at Monterey were all from Waikiki.
Also surprised to see they are a "big" aquarium trade item, I know of a handful of aquariums still keeping them. I also monitor the major wholesaler stocklists... nautilus seems to be a request item, not something constantly kept in stock. Seems like most aquariums have stopped exhibiting them due to the lack of captive bred animals.
I always love hearing these trip reports for precisely this reason... a lot of things goin' on out there I didn't know about...
Cheers,
Wyatt
Drew,
Undersea release them on the night dive at Admiralty Anchor which is in the vicinity of where there were trapped - albeit significantly shallower. The traps are lowered to anywhere between 100 and 300m (around 300m of line is let out) and the traps are basically on the reef. The area may not have corals, but it is still reef. I know Undersea lose their traps from time to time when they get snagged on the reef.
The recapture thing works both ways. There is an accepted method of estimating populations of animals through capture, tag, release and recapture. Let's say you capture 100 animals, tag them and release them. You then set your traps and capture another 100 animals of which say 10 animals were tagged. If certain other assumptions are met, you can estimate the population at 1,000 animals.
In reality it is more complex than that and there are a lot of assumptions that need to be made, but not recapturing all previously captured animals does not necessarily imply mortality of those not recaptured. It can mean that population is very large. It can mean that some individuals learn to avoid traps. It may also mean that at least some of the animals migrate horizontally as well as vertically. i.e. they move to a different are of the reef over time.
Wyatt,
They are largely scavengers rather than predators. They normally live in waters around 500m and have a vertical migration at night to shallower water, but they are still in fairly deep water (by diving standards) at night. It is believe they hunt around the deeper reef areas looking for animals that have died and fallen down the reef slope. They find their food mainly by smell (it is dark down there at night). I'm sure you would have seen this behaviour in your captive specimens. As they are fairly slow, I doubt they'd be particularly successful at catching midwater prey, plus they don't have feeding tentacles like those found in squid and cuttlefish which are needed for capture of fast prey.
I'm on dangerous ground here, but it looks like there are six species of Nautilus left. You folks with a penchant for the biological can back me up here or give me a better place to go look. 
