Second, less-predictable execution path. Additional cognitive load in evaluating effects across both paths. Additional opportunity for bugs. Doesn't necessarily mean that exceptions make all software which uses them unsafe, but does tend to mean that exceptions significantly complicate the task of proving safety for any nontrivial program.
I haven't done this, but probably the surest way to do that would be to use a proof assistant and extract the result to Standard ML or to OCaml. Standard ML has verified implementations, too.
Safe isn't the best word to describe it with. But it does mean that any expression or statement always has two possible control flows. You have the "surface flow" as well as the exceptional flow, so there's an added complexity.
I never felt this was a problem when I did Java though (despite their awkwardness - basically forcing coders to not use checked exceptions.)
Rust's control flow syntax for Results and Options are very similar to this but with an added benefit: you don't have to use the ?-operator.
panics is different, however. They are more akin to the way any Java program will happily OutOfMemoryError or NoClassDefFoundError given circumstances not (always) in your control.
I don't think panics are comparable to Java's VM errors. A lot of libraries (not just the standard library) seem to target panic-safety, avoiding unsafe behavior and resource leaks in case of panics. This means that the panic itself is not supposed to transition the process into an undefined state, like it happens with many VM errors in Java (where a stack overflow may mean that required cleanup action has not executed, for example).
With Rust, the overall situation is a bit strange: as a library author, you are expected to deal with the possibility of panics (which gives you all the headaches associated with dealing with exception safety), but as a user, you are not supposed to rely on them. (I expect that most request handler loops will have catch_unwind handlers, to avoid a faulty request taking down the entire process.)
I'm relatively new to Rust. I use panic (and cousins) in fn main only. As in: I'll expect(), unwrap() or similarly handle missing bootstrapping circumstances. Outside of main, I'll never ever use any of them. Even when I "know" that a condition is Impossible(tm).