Hi pledgeX,
Your organization is definitely not the first to encounter this problem. And while a caution against over-documentation is good advice in general, as you noted it doesn't solve the problem you face of having insufficient documentation. Companies vary in the amount of decision-making given to developers regarding requirements - some let developers handle more of the details, while others keep ownership of most or all requirements fully with the business. Either way, it's important to have everyone on the same page as you've discovered - and to have a way to document and sign-off on whatever level of detail is substantive for your company.
There are definitely ways to document requirements to the level of detail needed within your company, that leverage and extend upon your existing processes (wireframes, team reviews & discussions, testing / UAT considerations, etc.) - so you don't have to invest a lot of time & money, and don't have to re-engineer all your processes. You can put together fairly simple Word documents that incorporate and build upon the wireframes, along with business & UI rules, any relevant workflow steps, UAT scenarios, etc. This type of document can then be circulated, reviewed, and signed off by all parties involved. Here is a link to a blogsite that describes the sections and content for this type of document:
http://pathfindersoftware.com/2008/11/what-makes-a-good-requirement-document-for-an-agile-project/
This blog post highlights both the need for streamlined documentation from an agile perspective, but also the need for detailed requirements (down to validation rules and messages). Let me know if this blog provides enough information for you to move forward, or if you still have additional questions.
Important note: If your business users are not currently involved in reviewing or approving wireframes, you can run into churn by having these included in your requirements for sign-off. Business can get hung up on trying to redesign the wireframes, instead of focusing on the actual requirements. So be prepared to manage this - it's important to ensure that everyone understands what the wireframes are (and are not)...
Sandy