Possibilities:
1. Outgoing passenger records are only from 1890 onwards.
2. There will be little, or no, records of travel to Ireland, Isle of Man, Scotland, etc. Same goes for Europe.
3. Maybe he joined the Armed Forces. (Boer War?)
4. Perhaps he simply changed his name? (Deed Poll not necessary)