Supondo que você queira dizer que ambas as máquinas estavam se conectando ao mesmo servidor, provavelmente havia uma diferença de configuração que fazia com que o plano inadequado não fosse compartilhado entre as duas conexões.
Para que uma conexão reutilize um plano previamente armazenado em cache, algumas configurações (chaves de cache do plano) devem ser as mesmas, incluindo
ANSI_NULLS , ARITHABORT , Language , DATEFIRST e esquema padrão (se a consulta depender de qualquer resolução de nome implícita). Você pode visualizá-los em
sys.dm_exec_plan_attributes (aqueles em que is_cache_key=1 precisa ser o mesmo entre as conexões). Uma lista completa dos atributos em que
is_cache_key=1 é dbid_execute
required_cursor_options
compat_level
parent_plan_handle
date_format
language_id
status
merge_action_type
is_replication_specific
objectid
acceptable_cursor_options
date_first
set_options
user_id
dbid
optional_spid
optional_clr_trigger_objid
optional_clr_trigger_dbid
set_options e cursor_options são sinalizadores de bits que compreendem uma variedade de opções conforme documentado aqui
. Na minha experiência user_id na verdade se refere a schema_id(default_schema_name) em vez de principal_id . 
