BTW: I see the following on ICAO
http://www.icao.int/icao/en/assembl/a36/wp/wp059_en.pdf
but something doesn't add up. It claims that private pilots need a
second class medical, which I know is not true for international
flying

Might have something to do with the fact that FAA regulations != ICAO
regulations. In Germany, I did need a Second Class medical for my PPL(A).

ATPL/CPL: First Class
PPL: Second Class