From programmer's point of view it's not a big deal, it was done in ancient times even on C64 (Elite). Size alone is irrelevant, what matters is if the terrain is destructible or static (data that changes and needs to be stored).
From designer's point of view it's a problem, such planets will be empty and boring. Computer can never match hand crafted locations with rich NPCs connections, their stories and such (althrough, for topography alone it's quite good already).
Funny you bring up Elite. I loved that game when I was a kid. Supposedly they had to put in a couple exceptions in the code to keep it from generating star systems with offensive names.
I am not concerned with the possiblilty of procedually generating terrain. With the right sort of function I can make as much terrain as I want. As you say I'm concerned with any thing created by the computer that it would be boring.
I suppose that it may be sufficent to handcraft important locations, and then connect them with procedrally generated terrain. If you decide to explore the middle of nowhere you shouldn't be getting anything interesting (for the most part).