I only beat three bosses in NMH2 so I can't comment too much on NMH2's story. But I really did enjoy the story of NMH1.
The tale of Travis Touchdown is one of a misguided social outcast who is obsessed with masculinity. When he accepts the gig to be an assassin, he lives out this uber-alpha male fantasy of killing assassins all the way to #1 so that he can have some sexy time with uber-sexy Sylvia to over-compensate for being a beta male for the first 27 years of his life. Travis Touchdown basically represents every over-compensating geek out there. You know those obnoxious self-proclaimed "hardcore gamers" who are all like "casual gamers are pussies" "these new games these days are for pussies. If you can't handle these uber-hardcore video games like Ninja Gaiden, you aren't a gamer! Durrr"? A bunch of geeky nerds who talk all big behind a computer screen to over-compensate for their lack of masculinity? Well Travis Touchdown is like the wannable alpha male fantasy of those nerds. Travis Touchdown represents that. Ever single over-compensating nerd out there wants to be a badass like Travis and fuck beautiful women like Sylvia Christel. Because being a macho badass who fucks beautiful women, becomes #1 at what he does and brings home bags of cash is what every male in North America is programmed at birth (via social conditioning) to aspire to be. It's the American Dream.
Instead of challenging social norms of masculinity, those same social norms that have oppressed nerdy outcasts like Travis (who has been the beta male for 27 years of his life), Travis decides to embrace those norms head-on. Travis is a victim of the social brainwashing he has been subjected to all of his life.
The whole can't find an "exit" thing. It's a powerful message. Travis chases all of these status symbols of being an alpha male. The uber-masculine violence, the women, the money, the fame (look at the Death Metal boss fight in the first 20-30 minutes of the game. Travis refers to Death Metal's luxurious life as a paradise. And he fantasizes about being #1, being rich in a mansion like Death Metal with hot women, etc.). But then there is no end to that madness. These things don't fill the void in our lives. There is no real paradise to having acquired these things. This is what Death Metal meant, who had all these things (the badassery, the chicks, the money, the mansion, the rockstar fame), when he was telling Travis that this (his glamourous life) was no paradise. I think this is what Suda51 was trying to get at. This whole chase at the American Dream, was meaningless. That life is not about these symbols of status. All of these things are not your ticket to paradise. You can't find the exit with these things.
As naive as Travis seems though, I think deep down he knew that this rat race to #1 was all meaningless. That's why during the Death Metal fight he kept repeating "Can't find the exit, can't find the exit". Deep down Travis knew that these worldly desires didn't make life meaningful. But he just kinda went through the motions. As if he had no other choice.