Optimal cheating at BINGO

Mathematica, 302 bytes

(b=Prepend;i=1;n=15#&@@#-15+Range@5&;g=#~b~{N,0};o={#2,#3,#,##4}&@@#&;While[(l=Length@Union[t=(k=Take)[#&@@@g,i]])<5&&Max[#2&@@@Tally@t]<5,i++];If[l<5,m=#&@@Commonest@t;If[m===#,o[g~k~i/.{m,x_}->x/.{_,_}->Nothing],n@#2]&,o@DeleteDuplicates@b[n@#2,<|#->#2&@@@Reverse@g|>@#]~k~5&]~MapIndexed~{B,I,N,G,O})&

Unnamed function taking as its argument a list of ordered pairs, such as {{N,42},{N,34},{O,66},{N,40},...} (note that the first element in each ordered pair is not a string but rather a naked symbol), and returning a 2D list of integers, where the sublists represent columns (not rows) of the bingo board.

Output for the first test case:

{{1,3,2,4,5},{17,18,16,19,20},{31,32,0,33,34},{46,48,47,49,50},{62,63,61,64,65}}

In general, when the earliest possible bingo occurs because of a number called in each of the B/I/G/O rows, then those numbers will be in the center row; each column will otherwise contain the four smallest possible numbers (taking the already used number into account). For example, if the first test case is changed so that the second number called is B12 rather than B2, then the first column of the output board will be {1,2,12,3,4}.

Output for the second test case:

{{1,2,3,4,5},{16,17,18,19,20},{42,34,0,40,41},{46,47,48,49,50},{61,62,63,64,65}}

In general, when the earliest possible bingo occurs because of five numbers called in a single column (or four called in the N column), then the remaining four columns contain their five smallest possible numbers in order.

If the second test case is changed from {{N,42},{N,34},{O,66},{N,40},...} to {{O,72},{O,74},{O,66},{N,40},...} (only the first two entries changed), then the output is:

{{1,2,3,4,5},{16,17,18,19,20},{31,32,33,34,35},{46,47,48,49,50},{74,66,72,65,63}}

Somewhat ungolfed version:

(b=Prepend;i=1;n=15First[#]-15+Range[5]&;g=b[#,{N,0}];o={#2,#3,#,##4}&@@#&;
While[
    (l=Length[Union[t=(k=Take)[Apply[#&,g,{1}],i]]])<5
  &&
    Max[Apply[#2&,Tally[t],{1}]]<5,
  i++];
MapIndexed[
  If[l<5,
    m=First[Commonest[t]];If[m===#,o[k[g,i]/.{m,x_}->x/.{_,_}->Nothing],n[#2]]&,
    k[
      o[DeleteDuplicates[b[n[#2],Association[Apply[#->#2&,Reverse[g],{1}]][#]]]]
    ,5]&
  ],{B,I,N,G,O}
])&

The first line is mostly definitions to shorten the code, although g prepends the center square {N,0} to the input to simplify the bingo-finding. (The n function gives the smallest five legal bingo numbers in the #th column, 1-indexed. The o function takes a 5-tuple and moves the first element so that it's third.)

The While loop in lines 2-6 finds the smallest initial segment of the input that contains a bingo. (The third line tests for one-in-each-column bingos, while the fifth line tests for single-column bingos).

For any function F, the operator MapIndexed[F,{B,I,N,G,O}] (starting in line 7) produces the 5-tuple {F{B,1},F{I,2},F{N,3},F{G,4},F{O,5}} (well, technically it's {F{B,{1}},...}); we apply a function F that creates a bingo-board column out of its two arguments. That function, however, depends on which type of bingo was found: line 8 is true when we have a single-column bingo, in which case the function (line 9) uses the relevant input numbers in the bingo column and default numbers in the other columns. In the other case, the function (lines 10-12) uses the relevant input numbers in the center of each column and default numbers elsewhere.

JavaScript (ES6) 372 Bytes

Can probably still be golfed a bit, but I don't see how. Suggestions are much appreciated ;)

A=a=>[1,2,3,4,5].map(x=>x+15*a),F=a=>{b=[[],[],[i=0],[],[]],a.replace(/[^0-9 ]/g,"").split` `.some(x=>{b[--x/15|(c=0)].push(++x);return b.some((x,i)=>(d=x.length)>4||d==1&i-2&&++c>3)});for(e=[A(0),A(1),A(2),A(3),A(4)];i<5;a=b[i][0],b[i][0]=b[i][2],b[i++][2]=a)for(j=0;j<5&b[i].length<5;j++)b[i][j]<i*15+5?e[i].splice(e[i].indexOf(b[i][j]),1):b[i][j]=e[i].shift();return b}