I went to Network Solutions and put in:
thisdomainshouldbeavailable123.com
it was available, then tested by going to:
http://www.whois.com/
and it was not available.. under one min!
I tried a previous test with random garbage letters and it didn't take. they may have a filter to only register domains with dictionary words.
Fight the sneaky sneaks!