Trans-hydrogenation of alkenes Both this and that question seem to indicate that the hydrogenation of alkenes to alkanes or alkynes to alkenes is always a syn process.

However since hydrogenation is not a concerted process, I do not see why we could not have a non-negligible (although small) portion of the trans product.

Following this reaction mechanism for syn additions : 

before the penultimate step (the addition of the second hydrogen), can't the molecule simply rotate around the $\ce{C-C}$ axis (I expect this should be possible with small enough alkenes) ?

The Wikibooks article on alkenes does indicate that typically the hydrogenation of alkenes leads to only $98\%$ of the syn product, but I have been unable to find more precise information elsewhere.
This link has a good summary of hydrogenation. Syn addition is very much preferred because of the way the molecule 'adheres' to the surface. As you note, however, there are cases where anti-addition is observed - particularly for sterically hindered molecules such as 1,2-dimethylcyclohex-1-ene which shows up to 30% of the trans/anti-addition product (which also so happens to be the thermodynamic product).

The reason we see the syn-addition more often is because the Hydrogen atom attack happens really quickly (it's the kinetic product). If you pump more heat energy into the reaction though, you could expect to see more trans product - but this is dangerous as hydrogen is explosive.