##Perl, 93 bytes

$u=chr(65+rand 26).sprintf("%06d",rand 1e6),$_=`curl oeis.org/$u`while!/tt>(.*?)</;say"$u
$1"

Run it with -E flag (and I suggest redirecting STDERR, as curl prints its progression on it):

perl -E '$u=chr(65+rand 26).sprintf("%06d",rand 1e6),$_=`curl oeis.org/$u`while!/tt>(.*?)</;say"$u
$1"' 2> /dev/null

Explanations:
-$u=chr(65+rand 26).sprintf("%06d",rand 1e6) generates a random name,
-$_=curl oeis.org/$u tries to retrieve the sequence,
-/tt>(.*?)</ checks if a tag <tt> is present on the page (it's only present on valid pages). If so, it stores the sequence's elements in $1. And if not, the while keeps looping.
-say"$u\n$1" outputs the sequence's name and its elements.

Perl, 93 bytes

$u=chr(65+rand 26).sprintf("%06d",rand 1e6),$_=`curl oeis.org/$u`while!/tt>(.*?)</;say"$u
$1"

Run it with -E flag (and I suggest redirecting STDERR, as curl prints its progression on it):

perl -E '$u=chr(65+rand 26).sprintf("%06d",rand 1e6),$_=`curl oeis.org/$u`while!/tt>(.*?)</;say"$u
$1"' 2> /dev/null

Explanations:
-$u=chr(65+rand 26).sprintf("%06d",rand 1e6) generates a random name,
-$_=curl oeis.org/$u tries to retrieve the sequence,
-/tt>(.*?)</ checks if a tag <tt> is present on the page (it's only present on valid pages). If so, it stores the sequence's elements in $1. And if not, the while keeps looping.
-say"$u\n$1" outputs the sequence's name and its elements.