How much should we trust that the approach described in a paper solves the problem that it addresses as well as it claims to?
I think there is more than one type of "trust" here: "trust" as in whether to believe the authors are being honest, "trust" in terms of the state and certainty of knowledge in a field, and "trust" in the value of the peer review system.

Although misconduct is possible, and it is worthwhile to consider, another possibility is that the approach used in a paper relies on assumptions that were either taken for granted or are stated in the paper but you have overlooked them. For a signal-processing algorithm, for example, there may be an assumption that external noise has a particular color (white, pink, etc) - with a different color noise, or with real world signals, the algorithm may not work as well; for code optimized for a particular architecture you might get different results with different hardware or a different software environment. You shouldn't "trust" that a result in one context will apply to all other contexts that have not yet been tested.

Peer review is meant to improve the quality of and confidence in published material - it is not a flawless fact-checking system. Even when everything in peer review goes perfectly, the best you can assume from a peer reviewed paper or presentation is that the methodology is sound and the conclusions are reasonable based on the data. You should never "trust" a published work as the last word on a topic, and be wary of far-reaching claims - these are often stated for the potential of the technique, not necessarily the implementation as presented - these statements are intended to gain support for further work on the topic, so feel free to treat them with some skepticism. I wouldn't classify any of these as misconduct, just a potential for miscommunication between what is written and how you are expected to interpret what is written.

Lastly, the issue of sharing code differs by field, but at least in the biological sciences it has become standard for journals to ask authors to make analysis code and raw data available on request. I am not sure about the norms in computer science, and it certainly might depend on the potential for commercial application. It seems unlikely that someone would truly have "lost the code" to a recent paper, but if you are going back more than a couple years it is certainly possible that was indeed the case.

It is also possible, if you are a student, for example, that the authors felt your request was bothersome. How did you ask? "Can I see your code?" is a lot different from "I implemented the algorithm you published in 2014, and I got a different result from what you published. Here is the code I used - would you be able to share your original code, or have a look at mine to help find the discrepancy?" If you are truly skeptical, this is the approach I would suggest - science would benefit greatly from these types of replication and confirmation attempts.