If the number one answer to we're using Agile but it's not working is "you're doing Agile wrong", then maybe Agile isn't the solution?
The way I worked at the place that did not have an explicit process was one of switching between agile and waterfall methods. Early on in the projects, the process was primarily waterfall, defining things up front, building prototypes, laying out the project, etc. Then once passed that stage, projects would enter into a more agile or iterative process. Then as new big features came in, back to waterfall and then switching to agile once that stabilized. This worked quite well.