This is how I sorted Mine.
I have an Asus ET2221 All In One system.
Problem was same. Can't use recovery partition after Windows 8.1 update and received "recovery partition is missing message" in recovery system.
I have tried to access to built-in recovery system using F9 at start up but that seems corrupted by windows 8.1 too.
After everything sorted now i can't use built-in recovery but i can do everything again in order to recover the system if i need to.
Do your backup first before doing anything i explained here.
SOLUTION:
1-Prepare a UEFI Windows 8 (not 8.1) Usb stick.
2-Boot from USB stick by pressing ESC key at startup.
3-During windows 8 setup screens continue until you see partitions on screen.
4-Deleted Windows 8.1 loaded partition
3-Press enter to install a fresh copy windows 8 into this partition and wait patiently until installation finishes (takes 10-15 minutes)
4-After everything done and you see the main window of windows 8 restart the pc and boot from usb stick again.
5-Once windows 8 setup screen asking you for language selection, press SHIFT and F10 together to see command prompt.
6-At command prompt type DISKPART (enter) then LIST DISK (enter). At this stage look for the listed disk with highest capacity. It's generally the DISK 0 (if you don't have any other hard disk in your pc. Then type SELECT DISK 0 (enter) then LIST PARTITION (enter). Now you should be seeing the list of partitions with numbers. Probably the last partition is named as RECOVERY or OEM. It's capacity should be in between 4 to 30GB depending on your system. Usually a recovery partition takes that much space so you are not looking for something bigger or smaller than this. That partition has a number that you can see when you listed partitions. Type SELECT PARTITION 6 (the number 6 can be different in your system so enter the correct number of the partition). Type ASSIGN LETTER="R". This will temporarily reveal the recovery partition and you can access into it. Type EXIT to enter DISKPART but stay in COMMAND prompt.
7-Type R: and press enter. type DIR to see list of files and folder. I forgot how the folder named but it was something like ASUSRECOVERY or SYSTEMRECOVERY. If you don't have anything similar to this then do this. DIR *.WIM /S (enter). This will search the recovery partition and will give you a result where the WIM files kept. You will see the DIR command gives you the result that install.wim or xxxxx.wim is kept under R:\xxxxxxx\xxxxxx\xx\ directory. (x does represent the name of folder in your recovery system. Go to that directory by typing CD R:\xxxxxx\xxxxx\xx then press enter. now cursor should start blinking at this directory. Type DIR again to see list of files. If you see a lot of files then type DIR *.WIM to see list of WIM files. Look for the larger capacity WIM file if you have more than one WIM file. If you have WIM file to process than skip to NOW THE TRICK BIT section below.
But if you can't even find a WIM file then type DIR *.SWM to see where your SWM files kept. Now if you have SWM files then you need to combine them but in your recovery partition there is not much space left for combined output file. So i recommend you type EXIT at command prompt, go to partitions in windows setup, delete windows 8 partition only, This time create a new partition on unpartitioned space (you just deleted your windows 8 partition). Windows gives you an amount for all usable unpartitioned space. Lower this value by roughly 30gb and create the partition. Then create another partition on remaining 30gb usable unpartitioned space and format it on the same partition screen. Install windows 8 on larger space that you created before 30gb space. After windows installation finished like i explained before re-boot into windows usb stick press SHIFT F10 type DISKPART, SELECT DISK 0, LIST PARTITION, SELECT PARTITION X (X is the number of RECOVERY or OEM partition but not the 30gb space you created) then type ASSIGN LETTER="R", type EXIT. Go to that place where your SWM files kept. Before typing the command below find out which drive letter is for the 30gb space. it's probably D drive. type D: press enter. type DIR to see list of files. if nothing listed then look for the free space reported on screen after typed dir command which returned with no file to show. if it's 30gb or something close to this then you are in the right place and you can use this place for combined output file. type R: press enter. Type DIR *.SWM again. Now you should be seeing the list of SWM files. Their names are looking similar to each other but some of them has numbers. forget about the number but focus on the first file without number.
example file list.
file.swm
file01.swm
file02.swm
file03.swm
file04.swm
file05.swm
and so
to combine and extract the SWM files into D:\ drive as a single WIM file then type this.
imagex /ref file*.swm /check /export source.swm 3 d:\target.wim (i also explain the meaning of number 3 just below)
now the tricky bit
these WIM files has all the operating system files loaded into it along with recovery system and some other setup systems that i don't know at which stage the built-in recovery program is using. They are in the same WIM file but seperated and given a name. These names are called INDEXes. So once you do the following command type the correct index number. In my case the index number was 3. I managed to identify the index number using a software called WinNTSetup. The software works under a working windows. When my windows 8.1 was working i downloaded this software, again used diskpart to reveal the recovery partition then used WinNTSetup and choose that WIM file process. At the main window of it there is section called OPTIONS EDITION. There is a dropdown menu in there which shows the indexes in that wim file. The last index was named as FinalOS. That finalos was the 3rd option in the list and i assumed the index number of it was 3 and i was right at the end.
now the final bit
8-Type Dism/apply-image/imagefile:r:\recoveryimagedirectoryname(and this is something you see)\install.wim /index:3 /applydir:c:\ (so only thing you need change is the drive letter and name of the directory in red which is holding the WIM file)
this will dump everything into C: drive where your freshly installed windows stays in.
After process finishes in roughly 20 minutes type EXIT to exit from command prompt and close the windows setup to restart the system. When system reboots remove the usb stick.
This sorted out mine. Now my system is running fine without a single problem. If i need to recover my system i can do this again.
This might be lenghty and confusing. It took 4 hours for me to find this way.