[eluser]derekt[/eluser]
I've decided on a solution here, so let me share.
First off, thanks again jedd for your second reply, and you are completely correct that this isn't specific to photos - it's a more abstract issue about any "thing" that is unique but can be found in multiple places...could be blog posts, links, photos, whatever.
My main question has been what to call the "permalink". Based on your replies and the research I've done, the answer seems to be that each "thing" becomes a unique thing in each instance, wherever it may be listed. In my case, each photo a unique "thing" every time it appears in a category, thus it gets a separate URL.
Regarding the search engines, the exposure they provide is important to my goals for the site, so I've spent a lot of time researching how this works. It's my understanding that they basically apply "Ranking goodness" to a photo (which can be at multiple URLs). Obviously in a photo gallery UI, you're going to find multiple instances of a photo, and they are cool with that, but one thing you want to do is make sure they don't spread the "ranking goodness" across multiple URLs where the photo may exist: you want all the goodness applied to a single instance at a single URL. Long story short, the answer is that I should define for each image a "primary" permalink, then let programatically let search engines know to which URL the ranking goodness should flow.