10 million switching cycles with a hall effect sensor
wouldn't magnetism cause problems with EMC testing, CE and FCC rules?


Not if it is a tiny permanent magnet - fridge magnets are typically not FCC certified. A varying magnetic field is more of a concern.


  hall effect switch, are there any reliability issues


Not if the Hall Effect switch is from a reputable manufacturer. Adding the identified switch(es) to the question will help provide additional insight.


  Do permanent magnets loose some of their strength over time?


Some types of permanent magnet lose field strength due to impacts, but a tiny rare earth magnet will probably outlast the rest of the device by orders of magnitude.


  Are there any other good alternatives besides hall effect sensors?


That would depend on the purpose and application of the switch, but capacitive sensing lends itself to really long operational life, with the actual switching by a MOSFET for instance. 

There are many capacitive sensing products available, including some self-contained cap-sense pushbutton and proximity sensor (QTouch and QTouchADC) ICs from Atmel that do not even require a sensing  electrode, the IC itself works as the sensor. See these two references: 1, 2.

Another option is light path interruption sensing, such as using an LED and a photodiode, or prepackaged such sensors with both parts integrated.