So, I played a bit of Blood Bros. last night and after a few games made it to stage 2 on 1 coin. (continues are no fun!) It was also the first time I got to stage 2, and the first time I noticed the problem in the first picture (click it to expand).
After a few hours of debugging/hacking around I came up with a solution, it needed a little overhaul on the sprite/tile rendering code and order, and a priority buffer to keep track of the foreground/sprite relationships.