REA messages:
A Slot Revision Message may be sent in response to an REA message with a minimum inprovement of 5'
The MINLINEUP is the minimum time needed for that flight to get from its present position to airborne. 5' is the absolute minimum, 45' is the maximum.
If no MINLINEUP is specified then the taxi time valid for that aerodrome will be used (that can be up to 45').
To answer the original question the minimum line up time is not counted from the time the message is received, but considered when the new slot is calculated, e.g clock time 1000, MINLINEUP 10' earliest slot allocated will be 1010.
The slot normally takes a few seconds to appear on your printer, it's almost instantaneous. There have been occasions however when Comm centre problems for AFTN or SITA mean messages can be significantly delayed. Hopefully introduction of the CFMU internet application should end that particular problem.