They make it much harder to maintain single entry/exit in functions where you want that - and, crucially, harder to notice when a function isn't single entry/exit. They also violate referential transparency, which means e.g. caching the result of a repeated function call is no longer necessarily safe.
Not seeing this one. Unpredictable exception-throwing only happens if the work being done by your function isn't pure, i.e. it depends on something other than the function parameters. And if that's the case then caching its result is a bad idea anyway.
What am I missing here?
This isn't true. The canonical example is trying to grab the first element of an empty list. You either check and catch the error or eat the exceptional behavior, but some pure functions are just partial and aren't defined for all inputs.
(Whether or not they throw a catch-able exception depends on language/implementation and is really not relevant to my point.)
This comes up a lot in the Haskell community -- code outside IO is guaranteed by the compiler to be pure, but you can still get hit with an asynchronous exception because you called a partial function.