Solusi ditemukan oleh @Dan sendiri (tidak dapat memposting karena perwakilan)
Solusi yang saya temukan untuk masalah ini hanyalah menambahkan kata kunci "EXEC" ke kueri:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Solusi ini memperbaiki masalah dengan SQL Server 2005 dan masih berfungsi dengan SQL Server 2008 R2.