Решение, намерено от самия @Dan (не можа да публикува поради представител)
Решението, което намерих за този проблем, беше просто да добавя ключовата дума "EXEC" към заявката:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Това решение поправи проблема с SQL Server 2005 и все още работеше с SQL Server 2008 R2.