Improving performance when ordering by a column of a joined table
Let's start by thinking about that first query.
You're joining between Parent and Lookup, but it's an outer join, so Parents are never removed from the results. I'm going to guess that Lookup.Id is unique, so therefore, no Parent is going to have multiple Lookups that it joins to.
Therefore, the 50000th row in Parent (ordered by Parent.Id) is going to be the 50000th row in the results if we don't have the OFFSET clause.
Therefore, the query can move past the 50000 rows for the offset, look at the next 50 rows, and use this to join to the Lookup table. It doesn't matter if the join doesn't find anything, it's a left outer join and it'll just return NULL.
If you order by a different column in Parent, and that's indexed, it can move past those 50000 rows just as quickly.
Now let's consider the second query.
You want the 50000 rows that you ignore (by the offset) to be the first 50000 based on the results of the join. Those 50000 rows may include some that are NULL, where the Parent.LookupId value doesn't exist in the Lookup table. Even if you have a nice index on Parent.LookupId, you'll probably need to involve most of the rows, because unless you find 50050 rows that don't join successfully, you'll need to keep going. Even 50050 is way more than the 50 rows you join on in the first query.
Now, if you have a foreign key in place then things might be a little different. Then, the SQL engine ought to know that if it has a value at all, then Lookup.Name isn't going to be null. So it could theoretically start by finding the ones that are null, to see if there are 50000 of them. But that's still a bit of a stretch, and the SQL engine is unlikely to produce a plan like this.
But you could.
So to solve the performance of the second query, I would do a few things.
Start by considering the ones that aren't null. That means the rows which are part of an inner join. You can make an indexed view on this, so that you can have an index which is in the order you want.
But you will also need the ones where Parent.LookupID is null - except that for these ones, you don't need the join at all.
If you do a UNION ALL across these two sets (and maybe include a constant column in both, to make sure that the NULL rows appear before the NOT NULL ones in your order by), you should be able to see some improvement.
Something like this:
SELECT ID, Name
FROM 
(
  SELECT i.ID, i.Name, 2 as SetNumber
  FROM dbo.MyIndexedView i
  UNION ALL
  SELECT p.ID, NULL, 1 as SetNumber
  FROM dbo.Parent p
  WHERE p.LookupID IS NULL
) u
ORDER BY u.SetNumber, u.Name
OFFSET 50000 ROWS FETCH NEXT 50 ROWS ONLY;

Hopefully your plan will include a Merge Join (Concatenation) operator, so that it only pulls the rows that it needs from an Index Scan on the indexed view (in Name order) and an Index Seek on Parent (for the LookupIDs).