Stored procedure suddenly very slow, updating statistics not helping
I would suggest that you create a temp table or use common table expression to get the list of all longitudes you require from your remote Server and use the new temp table or common table expression to inner join with your FuelCalc table.

Something like below.

WITH CTE as 
(
select Longitude, MAX(SampleDateTime) as SampleDateTime, ShipLocationId, SHIPiD
        from [RemoteServer].[dbo].[Ships].LocationAttributes la
        inner join [RemoteServer].[dbo].[Ships].Locations l on l.ShipLocationId = la.ShipLocationId
        where l.SampleDateTime &lt;= timestamp
            and l.SampleDateTime &lt;= @ToDT
            and ShipId = @ShipId
        GROUP BY Longitude
)
select PK_ShipDataSubsystemConfigID
,timestamp
,cte.Longitude
,'Vessel Position Lng'
from FuelCalc
inner join ShipDataSubsystemConfig s on s.PK_ShipDataSubsystemConfigID =       FuelCalc.FK_ShipDataSubsystemConfigId
left outer join cte on cte.SHIPiD = FK_ShipId
where timestamp &gt; @FromDT
and timestamp &lt; @ToDT
and FuelCalc.FK_ShipId = @ShipId
order by timestamp desc