Can I trust a paper that hides implementation details?
As a researcher, I'm generally very keen on including as many implementation details as possible. However:


There is rarely the room available in a paper to describe every detail of an implementation.
Describing every detail of an implementation in prose often takes substantially more work than writing the program in the first place. The meaning of code (which is written in a formal language) is generally unambiguous; the meaning of prose (which is written in natural language) can often be ambiguous. Resolving the ambiguities in the prose takes time, effort and care -- it's often harder than writing the code.
Researchers are generally both very busy, and under a lot of pressure from above to produce quick results and move onto new projects. Resisting this pressure to bring existing work to a tidy conclusion is a good thing, but there are limits to how long you can spend doing this, and sadly the reward structure in academia provides little incentive to do it.


There is a reasonable case to be made that implementation is not valued in academia to the extent that it should be. However, even if it were appropriately valued, and even if there were no page limits for papers, there would still be an opportunity cost for individual researchers when it came to producing copious documentation describing the implementation details of their code. Human lifetimes are finite: the time spent describing every detail of old code could alternatively be spent coming up with and implementing new ideas. Some old code is so useful and valuable that it's worth spending a lot of time describing, but that's certainly not true in all cases. A lot of code (particularly hacked-together research code) just isn't that valuable in the long run: time spent describing it could be better spent on something else.

To directly answer your questions, then:


Yes, it's ethical to not describe every detail of your implementation -- most of the time, you can't, and of the times when you can, a decent proportion of the time it's not the best use of your time. Having said that, I'm of the school of thought that says you should at least make a reasonable effort to write good, clearly-documented code, to publish it on the web for all time (e.g. on GitHub) and to at least describe how the method works in a way that will enable someone reading the code to know what's going on.
If things in the code aren't in the original manuscript, start by reading and running the code to see if you can figure out what's going on. If it's not clear from that, do some reading around to see if other sources can give you any hints. If all else fails, and it's crucial that you understand the details, email the authors. If they ignore you, give up on their method and use something else.
The code can disappear from the author's page for a variety of reasons -- maybe they stopped paying for hosting, for example. If you need the code in that situation, email them. As mentioned above, good practice involves putting your code in a public repository so that it will hang around, but it's not unethical if you don't (just unhelpful).