Giải pháp do chính @Dan tìm thấy (không thể đăng do đại diện)
Giải pháp mà tôi tìm thấy cho vấn đề này chỉ đơn giản là thêm từ khóa "EXEC" vào truy vấn:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Giải pháp này đã khắc phục sự cố với SQL Server 2005 và vẫn hoạt động với SQL Server 2008 R2.