See this…
Computers that can be upgraded to use OS X Internet Recovery - Apple Support
It lists models that support 'internet' recovery mode, double check that you have the model correct, it can be easy to mix them up…
Identify the model of your iMac - Apple Support
Internet recovery can take a long time to load - after all it is getting the recovery system from the internet. Have a good intent connection (avoid wifi if possible - use ethernet). You need to keep the keys held & retry if it boots normally, it can take a few attempts.
OS X: About OS X Recovery - Apple Support
Frankly you may be better off creating your own bootable USB installer from an OS X installer downloaded from the store…
Create a bootable installer for OS X - Apple Support
Or use http://diskmakerx.com
That will allow you to repair the disk & do the same things that recovery mode does.
I can't say why your recovery mode is failing - a reinstall can fix these issues but it is impossible to tell why. Backup if you plan on reinstalling - normally it is fine, but a backup is a good idea.