Sql-server – why stored procedure performance is very high compared to plain select query

I have a table with more than 2 million rows, with needed indexes.

When I run a simple query it takes so much time so I decide to stop executing it; while when I wrap the query in a stored procedure, it runs very quickly (<100 ms)!

Also sp_executesql for the same query acts like stored procedure and runs very fast.

I just want to no why the plain query is slow? Is this normal?

I've indexed my table, so I do not think this is because of my lack of indexes

This is plain query:

SELECT  [t1].[Id]
    FROM    ( SELECT TOP ( 201 )
                        [t0].[Id]
              FROM      [dbo].[Logs] AS [t0]
              WHERE     [t0].[DeviceId] = 40
                        AND ArrivalDateTime >= '2012-10-12'
              ORDER BY  [t0].[Id] ASC
            ) AS [t1]
    ORDER BY [t1].[Id] ASC

This is procedure:

CREATE PROC TestProc
(
  @datetime DATETIME2(0) ,
  @deviceId INT
)
AS 
BEGIN
        DECLARE @dataTimeLocal DATETIME2(2);
        SET @deviceIdLocal = @datetime

    DECLARE @did INT= @deviceId;
    SELECT  [t1].[Id]
    FROM    ( SELECT TOP ( 201 )
                        [t0].[Id]
              FROM      [dbo].[Logs] AS [t0]
              WHERE     [t0].[DeviceId] = @deviceIdLocal
                        AND ArrivalDateTime >= @dataTimeLocal
              ORDER BY  [t0].[Id] ASC
            ) AS [t1]
    ORDER BY [t1].[Id] ASC
END

and Logs table:

CREATE TABLE [dbo].[Logs](
[Id] [int] IDENTITY(1001,1) NOT NULL,
[DeviceId] [int] NOT NULL,
[TypeId] [tinyint] NOT NULL,
...
other non related fields
...
[YearFa] [smallint] NULL,
[MonthFa] [tinyint] NULL,
[DayFa] [tinyint] NULL,
[Year] [smallint] NULL,
[Month] [tinyint] NULL,
[Day] [tinyint] NULL,
[Hour] [tinyint] NULL,
[DeviceLogNumber] [int] NULL,

CONSTRAINT [PK_Logs] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO

SET ANSI_PADDING ON
GO

ALTER TABLE [dbo].[Logs] ADD  CONSTRAINT [DF_LogsGs828S_DeviceId]  DEFAULT ((1)) FOR [DeviceId]
GO

ALTER TABLE [dbo].[Logs] ADD  CONSTRAINT [DF_Logs_TypeId]  DEFAULT ((1)) FOR [TypeId]
GO

ALTER TABLE [dbo].[Logs] ADD  CONSTRAINT [DF_LogsGs828S_ArrivalDateTime]  DEFAULT (getdate()) FOR [ArrivalDateTime]
GO

ALTER TABLE [dbo].[Logs]  WITH NOCHECK ADD  CONSTRAINT [FK_Logs_Devices] FOREIGN KEY([DeviceId])
REFERENCES [dbo].[Devices] ([Id])
ON UPDATE CASCADE
ON DELETE CASCADE
GO

Update1:

For some dates like '2010/10/10' in where clause query runs immediately but for some dates like '2012/01/10' it takes so long (19 secs)!!

This is execution plan of the query: