Smallest element distance between two lists

DistanceMatrix is fast. It evaluates multiple times in the SameTest. If you rewrite your code, you can see the difference:

min=Min[DistanceMatrix[testlist1,testlist2]];//AbsoluteTiming
{0.000501174,Null}
Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=min&)]//AbsoluteTiming
{0.0236643,{0.5}}

VS original code

Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=Min[DistanceMatrix[testlist1,testlist2]]&)]//AbsoluteTiming
{5.39343,{0.5}}

DistanceMatrix will stay in the future versions of Mathematica. Also you can find DistanceMatrix in HierarchicalClustering package or use this code.

Answering on your 3rd question, you can make it so:

mat=DistanceMatrix[testlist1,testlist2];
pos=Position[mat,Min@mat]
{{3,2}}
testlist1[[pos[[;;,1]]]]
{0.5}
testlist2[[pos[[;;,2]]]]
{0.4957}

mind[l1_List, l2_List] := 
 MinimalBy[Table[{k, First@Nearest[l1, k]}, {k, l2}], Norm]

RepeatedTiming[mind[testlist1, testlist2]]
(* {0.0061, {{0.0057, 0.}}} *)

For huge lists you may change Table for ParallelTable