This may be a case where you write a stored procedure to handle your cascading delete logic, and the EF code just makes a single call to the 'DeleteMyObject' sp and then your ef code will need to refresh its context to reload the changes immediately after.
You will pay a slight performance penalty to refresh your context, but if I had to guess moving the logic to an sp, and the performance gain of doing inter-related deletes there, will more than offset the small performance penalty of having to refresh.
Not sure if SP's are an option for you, but they are there to use when you need them.
EDIT:
Very simplified example of stored procedure that accepts the primary key of a table 'MainTable' and then deletes any related records, if they exists, from 3 'ChildTables'. You actual logic may be a bit more complicated:
CREATE PROCEDURE DeleteMyObject @Id INT
as
BEGIN TRAN
delete from ChildTable1 WHERE ParentId=@Id
delete from ChildTable2 WHERE ParentId=@Id
delete from ChildTable3 WHERE ParentId=@Id
delete from MainTable WHERE ID=@Id
COMMIT TRAN
Example of calling SP that is not mapped into your EF model:
SqlParameter param1 = new SqlParameter("@Id", 12345); context.Database.ExecuteSqlCommand("DeleteMyObject @Id",param1);
Further reading: http://msdn.microsoft.com/en-us/data/gg699321.aspx