If StartDate is a varchar column, then you cannot expect to get correct results when doing greater than comparisons on it. In effect, you are saying that any of the values that would be stored in the StartDate column should not sort after or on '20-JUN-10'. You should make StartDate an actual DateTime. So, until you do that, you should cast it to a DateTime and since it is only referencing the outer table, you can pull it out of the subquery:
Select ..
From TableA As A
Where ( A.StartDate Is Null Or Cast(A.StartDate As DateTime) < '2010-06-20' )
And Not Exists (
Select 1
From TableB As B
Where B.pid = A.pid
)
That StartDate is not an actual DateTime is a fundamental problem of data integrity and creates this problem along with a host of others I would imagine. However, if for some insane reason you have values that cannot be cast to a DateTime in your StartDate column, then you need to add yet another check (and slap the original DBA upside the head):
Select ..
From TableA As A
Where ( A.StartDate Is Null
Or (IsDate(A.StartDate) = 1 And Cast(A.StartDate As DateTime) < '2010-06-20' ) )
And Not Exists (
Select 1
From TableB As B
Where B.pid = A.pid
)