When is International Procedures Training required?
I have never heard of a specific "International Procedures"  program/rating. However, this was taken from one of the websites offering this training:


  "it will satisfy the training requirements needed for MNPS, RVSM,
  RNP-4, RNP-10, B-RNAV and P-RNAV Special Use Airspace approvals"


My guess is this course is offered as a bundle of MNPS/RVSM/RNAV training programs to the operators. 

For the operator to be certified to fly in MNPS airspace, they need to have a specific authorization from the regulating authority (in FAA they specifically need OpSpecB039) which in turn, requires specific training programs for the pilots. The same is valid about operation in RVSM,RNAV,etc.

There is no specific recurency training period; however, each approval certificate, for each specific operator, must include an approved 'initial and recurrent training program' which will specify the training frequency. At most, these periods must abide 
by the operator's program for proficiency check and line checks.

8900.1 4.1.4 98(d) 


  NAT/MINIMUM NAVIGATION PERFORMANCE SPECIFICATIONS (MNPS) AIRSPACE.  
  
  
  Each  aircraft is suitably equipped and capable of meeting the MNPS standards.
  The operator has established operating procedures that
  ensure that MNPS standards are met. 
  The flightcrews are trained and capable of operating to MNPS requirements.
  
  
  [...]
  
  All NAT/MNPS approvals are granted by issuing OpSpec paragraph B039,


ICAO NAT Doc 007 § 1.2.1 (I'm really not an FAA guy, somebody might find the Part 135 / 91 equivalent)


  All flights within NAT MNPS Airspace must have the approval of either
  the State of Registry of the aircraft, or the State of the
  Operator[...] These aspects include: the navigation equipment used,
  together with its installation and maintenance procedures; plus the
  crew navigation procedures employed and the crew training
  requirements.
  
  The ICAO doc goes on to further detail what that training should include (1.3.8 - > 1.3.12), but does not specify a training frequency or the need for recurrent training.


Appendix G to Part 91: Operations in Reduced Vertical Separation Minimum (RVSM) Airspace
Section 3 Operator Authorization 


  (b)An applicant for authorization to operate within RVSM airspace
  shall apply in a form and manner prescribed by the Administrator. The
  application must include the following:
  
  (2) For an applicant who operates under part 121 or 135 of this chapter or under subpart K of this part, initial and recurring pilot
  training requirements.


AMC1 SPA.RVSM.105 RVSM operational approval


  (c) Training programmes, operating practices and procedures :
      The operator should submit training syllabi for initial and recurrent training  programmes together with other relevant material.