PowerShell 6, 244 bytes

De Bruijn sequence is a good idea. Thanks to Level River St

param($w,$h)for(;$z='A'..'Z'|?{"Z$x"-notmatch-join"$x$_"[-2..-1]}){$x+=''+$z[0]}$v=random 9 1..$h|%{$y=$_+$v ,(($r=1..$w)|%{"\ $($x[$y+$_-1]) /"})+,($r|%{$x[$_-1]+' X '+$x[$_]})+,($r|%{"/ $($x[$y+$_]) \"})|%{$_-join' | '} ,'-----'*$w-join'-+-'} 

Try it online!

1. I've adapted my answer from the topic Generate the shortest De Bruijn for the case {String:'A'..'Z', n:2}.
2. The script loop by this sequence twice: each tail take two chars by row and by column
3. The shortest De Bruijn sequence contains 676 chars. That's enough for 255 rows and for 255 columns
4. The script add random 9 to row numbers to comply with the random requirement

No-duplicate test generates #### strings instead ASCII tails and is looking for duplicates.