The stored procedure would error when trying to query the linked server that was down. It should recompile ok as the linked server itself is there

You could possibly do a check in the stored procedure to see if linked server was available first before querying. Here's an example

http://blog.h2consultants.com/2012/test-to-see-if-linked-server-is-available

I've not used this stored proc myself before so might want to test, especially to see how quickly it returns when testing a linked server that is not there.