well if you must have the holes the best I can sugest is keep the outside curve, make the holes and build the faces out from the holes to join with curve, it will be boring but you will get a clean mesh

have fun

ps I wanna see the pic lol (if I can) cant think of a pic where the flipflop is the important bit ;-)