Any Traps I've laid out for the encounter deck obviously don't attach to Black Riders, but what happens to those Traps? Do they fail to attach and get discarded, or do they lay in wait for the next valid target?

If a non-eligible enemy is added to the staging area it simply stays there until an eligible enemy is added. Think of it as "attach to the next eligible/legal enemy that enters the staging area".