Reduction in Service Ceiling / Change in RVSM
1(a). Yes, in the US, below 18,000 feet and above 3,000 feet, airspace seperation is 500'.

3,000' and above to 18,000 feet:
IFR traffic, eastbound fly at odd thousands
VFR Traffic, eastbound fly at odd thousands + 500'
IFR traffic, westbound fly at even thousands
VFR traffic, westbound fly at even thousands + 500'

(I always figured that was because "east is even" would be too easy to remember.  JUst like Nav lights, red is in the left because "red on the right" would be too easy to remember. Red/Green is likely a carryover from boating tho.)

1(b), I don't know about Europe.

2 I believe service ceiling is more a factor of jet engine efficiency and aircraft drag.  Piston engine's need to be turbocharged or turbonormalized (make sea level power at altitude) to make the high teens need to make air denser for the engine to make power - if you can get up there, the drag drops a lot and you can go a lot faster.  Jets are big compressors in essence and can make all the dense air they need to burn jet fuel with.

Why don't more jet arcraft fly higher? Maybe it's not worth it drag reduction-wise, or time savings enroute-wise, to climb higher and then to descend back down.