Why does SQL Server fail to create a procedure referencing a linked server?
Some objects are allowed to be created to facilitate Deferred Name Resolution. The assumption is that if you create a procedure that references dbo.MissingProcedure, you will create dbo.MissingProcedure some time between the moment you create the procedure, and the first time you execute it. Another situation that works is a table that doesn't exist yet. I can say the following, even if dbo.table_name doesn't exist:

CREATE PROCEDURE dbo.procedure_name
AS
BEGIN
  SET NOCOUNT ON;
  SELECT column_name FROM dbo.table_name;
END


Again, because SQL Server is giving me the benefit of the doubt in this case. But it doesn't always. If dbo.table_name exists, but does not (yet) contain a column named column_name, I'll get an error:


  Msg 207, Level 16, Procedure procedure_nameInvalid column name 'column_name'.


SQL Server validates the column names if the object exists, just like it validates the remote server objects in your case - which it can't do, because the login doesn't (yet) have permission.

Now, why SQL Server is implemented such that it lets some things slide and not others, you'll have to ask the dev team. Erland Sommarskog has some great ideas on giving us the option to make the behavior more consistent; you should read Ideas for SET STRICT_CHECKS ON and vote for - and comment on - his Connect item.