Cfrtjryk

I had Ubuntu and Windows 10 dual boot, working perfectly fine. Due to slow performance of Ubuntu on my machine, I wanted to replace it with Elementary OS, while maintaining the dual boot.
I fired up the E OS iso, chose something else, removed the ubuntu partition and created a new one and installed elementary on it. Theoretically, it should have worked.
When I restarted I directly booted into Windows 10. I knew that bios might have placed windows as higher priority boot than Linux. So I went to bios and changed the order.
Now, it landed me on grub prompt. I used this command to boot into Elementary:

set prefix=(hd0,7)/boot/grub

set root=(hd0,7)

insmod normal

normal

And I was greeted into Elementary OS. Now I ran:

sudo update-grub

It went fine and I restarted the laptop, thinking that it worked!
Next thing, I was again dropped to grub prompt. When I entered the above command to boot into Elementary, grub menu appeared! It worked with all the entries (I could boot into Windows and Elementary OS)

I did a google search and ended on finding that I haven't ran sudo grub-install /dev/sda. So I went over to Elementary again and ran it. It gave me an error, saying that 'GPT partition labeled 'bios boot' could not be found' (similar). Again googling for some time resulted with, I needed to create a new partition with 'bios_grub' flag. (Why? It used to work earlier without such thing.) Did it. Still problem stays same. (I can still boot into Windows using BIOS or by entering the command at grub prompt and boot into either two!)

Edit:
I saw this answer while writing this question and thought of giving it a try.
But, I don't have a grubx64.efi in my /boot/grub directory! I thought maybe I didn't install the OS in EFI mode, but running dmesg | grep "EFI v" gives
[ 0.000000] efi: EFI v2.31 by American Megatrends.

The partition with the bios_grub flag is only for situations when you want to use a legacy MBR-style bootloader on a GPT-partitioned disk.

You should check the /boot/grub/device.map file and make sure it identifies as (hd0) the disk that will actually be (hd0) when you're booting Elementary OS. Do this before reinstalling the UEFI version of GRUB (see below).

The UEFI bootloader file is not necessarily named grubx64.efi: it could be just grub.efi, or basically anything.efi. Run efibootmgr -v to see the exact pathname that is used by UEFI to load the UEFI GRUB bootloader. The pathname will be relative to the root of the EFI System Partition (also known as ESP partition): it is a small FAT32 partition that also contains the Windows bootloader. The efibootmgr command will typically display the boot file pathnames using the Windows backslash convention, rather than using Unix/Linux-style forward slashes.

Some Linux distributions won't mount the ESP partition at all by default; they will only mount it whenever needed to reinstall the bootloader. Others mount the ESP partition to /boot/efi. If the ESP partition is mounted there, then the full pathname of the Windows UEFI bootloader as viewed from Linux would be /boot/efi/EFI/Microsoft/Boot/bootmgfw.efi.

The UEFI standard mandates that the bootloader should be located in /EFI/<vendor name> sub-directory of the ESP partition. So the UEFI GRUB bootloader for Elementary should be at /boot/efi/EFI/<something>/<something>.efi.

It seems like the grub-install command on your system attempts to install a legacy-style GRUB bootloader, at least by default. Perhaps you'll need to use --target option like sudo grub-install --target=x86_64-efi /dev/sda to explicitly specify that you're (re)installing an UEFI version of the bootloader?