Sometimes NAT matters and sometimes it doesn't; I can't quite understand why I need it sometimes

You normally dont require NAT for internal segments unless they're overlapping, something that happens commonly when connecting through IPSec for example.

If you're SNATing the traffic, its using the LAN interface of the firewall which is the gateway and SHOULD work always. When not using NAT, it might be that the devices on the other segment have some intermediate device thats routing the traffic to other place, you could double check that with a trace route. Anyway, for internal vlan traffic you shouldn't require NAT unless something is configured wrong in your enviroment.

Hope this helps, cant help much without info on the environment.

You normally dont require NAT for internal segments unless they're overlapping, something that happens commonly when connecting through IPSec for example.

If you're SNATing the traffic, its using the LAN interface of the firewall which is the gateway and SHOULD work always. When not using NAT, it might be that the devices on the other segment have some intermediate device thats routing the traffic to other place, you could double check that with a trace route. Anyway, for internal vlan traffic you shouldn't require NAT unless something is configured wrong in your enviroment.

Hope this helps, cant help much without info on the environment.

Thanks - it kind of makes sense and sheds some light. I ran a tracert from a computer on one segment to a computer on another segment and it's one hop to the server - the one hop is the default gateway of the calling computer. 

I am doing some more research to see what is going on.