Is the Bloodstained Letter bugged?

I've been farming Act 3 for keys lately, and the Keep Depths are where I go to build stacks. To answer your questions:

1. Yes. There are lots of dead soldier corpses, and as you noted, the distinction is that the one holding the Bloodstained Letter is a Dead Soldier, not a Dead Guardsmen. I have always found him on the Keep Depths Level 1.
2. I've found it extremely rare that it doesn't drop. My last run had the Dead Solider a couple rooms in. Usually, he's in a little alcove dead-end.
3. I've noticed I get the Bloodstained letter almost every run. Now that I'm paying attention, the Dead Soldier has (so far) dropped the Bloodstained Letter every time.

There is a real bug related to this issue and I now know the parameters of this bug. I have run into it myself while playing the game on the Xbox 360. The game was originally released on the PC on 2012-MAY-15. So, it would appear that Blizzard could not reproduce, find or fix the bug by the time the game went gold for release on the consoles on 2013-SEP-03. Here's how it goes.

1. It's not a bug directly related to the Bloodstained Letter in itself (keep reading).

2. It a bug related to the tracking mechanism for the Challenges (or PC Achievements).

When you read a lore book or talk to someone at least two things happen (hopefully in quick succession)

a) The item (book or conversation) gets flagged as done. For example, conversations listed for a Follower or NPC will display as grayed out.

b) Any associated challenge (or achievement on the PC) then gets tripped, and viola... you get a checkmark or the challenge pops up on screen.

For some reason, a particular item can get flagged as done (a), but not trigger the associated challenge (b). That's the bug.

3. How do I know?

I have seen a few times where I have had a conversation with a Follower and then when I go later to check if that conversation has a checkmark beside it in the associated Challenge it does not. But when I go back to that Follower I find that that particular conversation is in fact grayed out. Step "a" was accomplished, but "b" was not. Fortunately I can have that same conversation with that Follower again by clicking on it again (even though it is grayed out). I look at the challenges again and the conversation is checked off now. I have also seen where I have completed an item (conversation or lore book) but there was a delay before it registered in the challenges. When I first checked the challenge it did not register, but I wait a bit and look again it is now has. My point is, there is a problem going from step "a" to step "b" and it is fundamentally a challenge tracking bug.

4. How this is exacerbated with the Bloodstained Letter

With the same character you can imitate the same conversations multiple times. So, if the challenge doesn't register the first time, you can have another shot at it. If the conversation is still listed for the associated character you can just play it again (though it's probably grayed out), If it isn't listed anymore, you can go back and replay an earlier level where it is listed (by selecting the level from the main menu). This is not possible with lore books. Once a lore book has been read, meaning step "a" has been completed, it does not drop anymore. The bonus for most lore books is that they have multiple spawn points. Coming back to the same level and hitting a satchel will usually drop a lore book in the series you haven't read yet. Some you have to read at certain points or levels in the stories progression (such as Leah's journals), but again, you can replay these levels.

The problem is exacerbated with the Bloodstained Letter however. It will only drop on the Dead Soldier (single spawn point), wherever he is found in Bastion's Keep... assuming that step "a" is not flagged as done yet. Once step "a" has been done, it will never again drop with your present character on any mode (Normal, Hard, Nightmare, or Inferno). In other words you have ONE chance only to get this letter. If the challenge bug impedes registering that it actually happened (i.e. step "b") you can't make it happen by re-playing the level. With "a" already flagged, the Dead Solider will simply drop gold (if anything). The only way to get the Bloodstained Letter to drop again, is to play the game with another character that hasn't completed step "a" yet. Play the new character all the way to the Act III Quest, "The Breached Keep". It is unlikely that the bug would kick in on this other play-through, but it could.

Of course, if you never did find the Dead Soldier in the first place and never did get the drop, you have a chance to get it if you replay the area. That assumes that step "a" hasn't happened yet.

In my case, I am pretty sure I heard the dialog for the Bloodstained Letter as it was read aloud on my first time through the area. I was just in the middle of battling monsters at the time and wasn't paying a lot of attention. Somewhere along the way I noticed that I didn't get the checkmark for the Bloodstained Letter in the People's Lore challenge. I replayed the level too many times to count, hoping I would eventually get it. But then, when I looked at what the letter contains I remembered hearing it. I considered my experiences with Follower conversations and put it all together. Now I too am virtually locked out and unable to complete the People's Lore challenge, both a nuisance and extremely frustrating - especially since I actually read the letter in-game at least once. The tracking system missed it (as a result of the bug).

Bottom Line: It is all related to a very real bug with the challenge or achievement system that doesn't always register an item has been done. It is a particular problem with the Bloodstained Letter because you don't get a second chance at it with the same character. You are pretty much toast if the bugs kicks in and you miss it. Simply replaying the level will NOT get it for you, no matter how many times you play it (UNLESS you completely overlooked the Dead Soldier when you went through the level). The work-around that some have described works is to play the game again with another character and hopefully you will get it this time when you get to the Bastion's Keep. Other items can be affected by this same bug, but in most cases, farming the area or initiating the conversation again will get the desired results. Not so with the Bloodstained Letter.

Hopefully with this additional data, Blizzard can reproduce, find and fix this bug and a patch will be supplied so a separate play-through with another character is not necessary if you miss it the first time. And hopefully this also provides all you users with enough explanation so you know what you can and cannot do until it is fixed.

I tried to post this on Blizzard.net, but I don't appear to have a FULL account. I tried something else, but I don't know if it worked.