I do not have any thoughts on the first problem (the beam comes off the structure in an upward trajectory).
For the second problem (beam falls through stationary structure), yes: it either has to be difficult (meaning the user needs to setup the model) or it has to be a really, really long analysis runtime (meaning the software applies the most complicated settings to every option in every analysis.) 
My thought for the second problem is related to the mesh size. "Surface to Surface" contact is a bit of a misnomer: it is really detecting when the nodes on surface A make contact with the element faces on surface B. This is the "Contact Type" of "Point to Surface" which can be controlled under the "Options" for the surface-to-surface contact. If the user or the software has chosen the "Point to Surface" method, it is possible that the nodes on surface A do not touch the element faces on surface B when the mesh on surface A is too large; as a result, the bodies pass through each other. See the illustration on the page "Nonlinear Analyses > Loads and Constraints > Surface-to-Surface Contacts > Options" in the documentation. (This link goes to the page in the 2014 Help, but it should be close enough for whatever version of Simulation you are using.)
One of these may be the solution to the second problem:
- Use a smaller mesh in the area of contact so that there is always a node on each surface making contact with the adjacent element faces. Then it doesn't matter (as much) which surface uses the "point" and which one uses the "surface".
- If the software is using point to surface contact, you can switch the order of the parts so that which body uses the "points" and which uses the "surfaces" are reversed. This may help depending on the mesh size. (Which contact pairs are using "Points to Surface" and which are using "Surface to Surface" is shown in one of the log files, where it lists how many elements are in each part, just before the iterations begin.)
- Force the software to use the "Contact Type" of "Surface to Surface". This really just detects contact between the nodes on surface A with the element faces on surface B and the nodes on surface B with the element faces on surface A.
If you want to post an archive of your model (especially the model with first problem), someone may be able to take a look at it. See "Create, Post, or Provide an Archive of your model".