You need to tell `aptitude` not do do any special column formatting.
> \--disable-columns
>
> This option causes **aptitude search** and **aptitude versions** to output their results without any special formatting. In particular: normally aptitude will add whitespace or truncate search results in an attempt to fit its results into vertical “columns”. With this flag, each line will be formed by replacing any format escapes in the format string with the corresponding text; column widths will be ignored.
So do this instead:
$ aptitude search '?virtual' --disable-columns|grep ^v |grep -v i386|sort|uniq
v a52dec -
v a52dec-dev -
v aac-tactics -
v aalib1 -
v aalib-bin -
v acl-dev -
v ada-compiler -
v aide-binary -
v alphy -
...