[eluser]adamfairholm[/eluser]
Well, even though this didn't quite get solved the way I wanted it to, it did get solved, so I'll share the "solution".
Although I wasn't able to look at the Apache headers, in my conversations with the support members for the host of the site, they were stumped and said that it appeared to be a problem with Code Igniter.
My own tests confirm what Randy is saying, however, that Apache is doing something to mess with the headers. I found that if I created a file with any extension outside of Code Ingiter and sent a Last-Modified header, it came through fine.
However, with any URL that is a directory (accessing the index file) or a URL explicitly accessing the index.php file, the Last-Modified comes up as the Last-Modified date of that file. So the same essential behavior exists outside of Code Igniter as it does inside.
Moving all the code over to another server worked fine, but didn't solve the problem of that server acting up. The hosting support wasn't able to find out what was causing the problem on the server's end.
Soooo I realized that all the feeds were being published with an extension anyways (that didn't need to access an index.php), so I recreated the RSS and Atom parsers outside of the CI structure. (I have to admit it was a bit of a shock going back to straight PHP for a bit - I never realized how much I take for granted now that I know how Code Igniter saves so much time). I just included a line in the .htaccess to allow the .xml files to be parsed as PHP and away we go - everything worked flawlessly.
Although it is inconsequential for the site, I am still bothered what with Apache is causing it to say "hey, looks like you are trying to send a Last-Modified header. But we've got something totally better. It's the Last-Modified header off the index.php file you're accessing. Trust me, you'll like it." It keeps me up at night.
Thanks to Randy for the help in identifying that it wasn't CI or .htaccess as I was thinking.