Like most things, the easiest way to create other ways to achieve an effect is to examine and find what aspect of the original example causes that effect. In this case, the player feels as if they are failing because they are primed to have the expectation that bad things in video games are their fault. This is because most games reward good performance with good results. Unfortunately, and as you guessed, this is a rather short-term (or cheap) method of evoking the feeling of failure because it relies on our cultural expectations of games, which could change at any moment.
Instead, you can use the most basic function of the brain to help you: Association. Whenever two event occur simultaneously or even just temporally close together, a brain immediately attempts to find which caused the other, unless prior knowledge says something else did. Here is an example...
In Generic game 2015, the main protagonist Bob shoots his generic spaceship at generic aliens. If the player gets over 20,000 points in a level (a somewhat difficult feat), then the attack is successfully repelled. On the other hand, if Bob acquires less than 15,000 points, the aliens will destroy a building located in the background. If the player does poorly, they know by the loss of a building. This is a successful priming.
What this means is that in player's mind, any time a building falls, the player is not doing well enough. You now have a tool to toy with their mind because, any time the event of a building falling is triggered, the player and their association will trigger the feeling of failure whether or not it is justified. (stifled evil laugh) Its probably useless at this point to say you can make building start destroying themselves and still achieve the same illusion of failure.
But there are two last things to take note of.
The first is about player knowledge. If you want the player to feel like they failed without them actually failing, the mechanics have to include that. When the mechanics include the fake fail, it gets put on a wiki. Finally, the player reads the wiki, and no longer feel any failure at all. But their is a partial solution to this.
While security through obscurity is completely hopeless, you can utilize randomness so that even if the player knows all your algorithms to a T, the game can generate a situation that the player is still unsure whether or not the failure queue is their fault or not. Maybe the game has chosen to drop buildings even when you gain enough points, or maybe it actually is that your failing.
The exact example I have given is a somewhat weak one. Ideally, the failure trigger should be woven into the narrative for greater effect (because that is where the characters and other objects are that carry emotional attachments). Eg: If each building being destroyed contains an important member of the story-line.