Sorry - I missed the bit in your first post that said you moved in February!
To be honest in this case it does sound like he is intimidated by another cat out there. It can happen even if you don't see the other cat much for instance if that cat scent marks a lot in your garden. Also if he had a negative experience when he first started to go outside in those early days.
The fact that he is interested and looking outside is very positive though.