This will pick random rows from your table without regard to the sequence of the [NewAccountID] or [Random] columns.
;with cte as (select row_number() over(partition by accountid order by newid()) as rowID,* from #a)
select * from cte where rowID = 1
This generally performs well with sets of rows numbering up to tens of thousands.
If the NewAccountIDs are not interleaved with AccountID, you could also get min/max values of NewAccountIds and randomly pick a row from each range.
__________________________________________________
Against stupidity the gods themselves contend in vain. -- Friedrich Schiller
Stop, children, what's that sound? Everybody look what's going down. -- Stephen Stills