>>and with no plugins and no themes installed, there is no option to enable featured images.<<
You HAVE to have a theme installed. If you don't have a theme installed, then you'll absolutely not have featured images (or anything else for that matter, like menus, headers, etc). You have to activate menus and featured images in the functions.php file *of your theme*. if the theme doesn't enable it (or it's too old to have that feature), then you won't have the feature.
the line is this:
add_theme_support( 'post-thumbnails' );
if that's not in your theme's functions.php file you won't have it. It *is* in the default twentyten and twentyeleven themes.
If you had featured images at one time, the images are still in your database - it's either a plugin or a theme that's installed that is conflicting/removed the feature. You just have to add it back in to pull everything out like it was before.