For me, it's not really a science to much as it is an increase in confidence. As I'm going through the process of designing and testing, eventually the product/thing begins taking shape and as it does so, your awareness of how "ready" the product is comes to light.

I find that a nice gauge of this is what client feedback is about (if you're a consultant). A silly example would be if you've moved away from talking about what you want to present in an interface and start talking about things like icons, you're probably ready to move into visuals. Don't forget that visuals are not "styled wireframes"—layouts and concepts can change here too sometimes.

Another note I would add is using something like the "double diamond" approach to product definition and design. By going wide and then converging, and then going wide again, you're able to track how broadly you're thinking about a problem before finally being sure that your solution is is appropriate and is not missing anything. Also see Paul Laseau, circa 1980.

EDIT: You mentioned focusing on data. This is something I've had to deal with previously, with certain clients being unable to separate content from structure. I would consider reminding them that the intent of a wireframe is to define structure, interaction, and flow; and that individual data points can be changed in development as long as the structure remains in tact.

As long as needed? What kind of question is that? You move to Photoshop when you feel confident about what you have. And if you're not done, what exactly are going to do in Photoshop? Why is there supposed to be a specific duration for this?

At my last job we ran our usability tests on the wire-frames so we ended up spending a lot of time in IA. Felt like 60/40 IA to visual design.

Depends on what I'm working on but generally, it's probably around 20-30% of my time. I prefer to get the basics of a flow down at wireframe level but it ends up being refined at mock-up level anyway.

I try to get working in code as soon as possible, so prototyping doesn't take much time in my process.

I spend three or four hours on first drafts to get time estimates and find out application complexity — this helps to define project budget range.

After that wireframing takes from one day to about a week (depending on project complexity). Further thinking and refining are made in a working prototype (or an app) already. When using agile and scrum it doesn't become a problem.

I've posted an article about my wireframing process here about a month ago, maybe it'll be interesting for you.

I work on a product that has been around for around 4 and a half years and rarely goes through visual updates. Given that, we probably spend 80% of our time on feature definition, flows and wires per feature.

It really depends on the scale of the project. I honestly find that the less complicated the architecture sometimes Ill spend as little as 10% of the time on wireframes. I think sometimes their utility is overstated. For me it also depends if I am working more with an engineering team vs. a client.

Large or information rich projects really benefit a lot from them IMO and 50% of the time then makes a lot more sense.

Same here, about 40% of every project (internal or external) is consulting, meaning discovery and wireframes. Then another 10% of consulting at the end confirming why we made those decisions at the start of the project. From experience, I now constantly reiterate what we discovered during the early phases when presenting milestones. For example: The solution we came to for multiple user login home screen is shown here, here, and here.