perl -ne '/^([\w\-]+): (.*)$/ and ${$1}=$2;next if (/^ \.$/ and $l=1
);print "$Package $Version\n" if $l && /^$/;$l=0;' /var/lib/dpkg/available
or, shorter but not as future-proof:
perl -ne '/^(\w\w)[\w\-]+: (.*)$/ and ${$1}=$2;next if (/^ \.$/ and $l=1
);print "$Pa $Ve\n" if $l && /^$/;$l=0;' /var/lib/dpkg/available
--
_ivan