I think the first mistake was Paul Anderson. Predators building pyramids and being treated like Gods goes against pretty much everything we knew of the creature beforehand. Anderons concept was B-movie stuff. The biggest mistake of his was to make the Predator 'the lesser of two evils' and shoe-horn the character into an anti-hero role. Anderson did not get the Predator at all and killed all the awesome primitive/futuristic vibe the character had.
AvP being PG-13 certainly didn't help, as did having no decent characters either. No two ways about it, AvP is a mediocre film that made the mistake of being a comic-book movie rather than a cinematic cross-over.
AvPR rectified a few of those Predator issues but replaced them in turn with a whole host of new ones.
Mystery is everything in horror, yet there is a core of fans who want to enjoy watching the creatures battle it out.
That's the versus bit...and its the problem! The aliens and the predators are no longer doing what they were meant to do...which is to be scary and kill off characters you'd grown fond of.
Once you start liking Freddy Krueger, the nightmare is over imo.
Alien Vs Predator should have always been Alien Vs Predator, Aliens+Predator versus humans. The Strauses got that dynamic right but showed us far too much of the Predator in the process.
My suggestions are:
Alien Vs Predator should be set in space. (The Predator integrates into the Aliens universe far better than vice-versa)
It should further the Aliens mythology (anything from the Alien 3 unmade scripts would do) and then bring in Predators in Act 2.
I can't help but picture watching a great Aliens movie, where the invisible guys show up and start blowing holes through everything they see
That said...I strongly believe an Alien Vs Predator film could never have been as good as a stand-alone. You lose the purity of the haunted-house/slasher structure with the versus stuff. A long-story short, I think they need to make an Alien AND Predator movie in the first instance, and leave the versus stuff until the climax.
Another way to do it, seeing as we've got two movies now already, is to go for all-out spectacle...but that would need a mega-budget.
I doubt we'll see another AvP movie again.