Gray market does not always imply warranty problems. Some companies honor warranties worldwide. Canon is one of them. Nikon is not.
And by the way, the street prices are often significantly higher in Europe than they are in the US - but that usually includes high VAT. It must be that wholesale prices are much lower to make importing the cameras to the US worthwhile.
The really good prices you find are usually not because the products are gray market. They are usually places who intend to rip you off in one way or another. Several of the places in Rupp's list from pricegrabber fall into this category. Some people may have not problems - others will have significant ones.
A common ripoff scheme, from places that will actually send you the product you order, is to charge you extra for things that normally come with the camera. So, the price they show is for the camera, but if you want batteries, battery chargers, manuals, etc. you will have to pay extra. These are things that are included in the box.
www.dpreview.com has been recommended as a place to find out about cameras you're interested in - and it is. It is also a good place to go to search for places you are thinking about buying from to see what other people think. You will find a lot of stories about places to avoid.
However, you will also find negative stories about very reputable dealers which I would have no problem recommending. These include
B&H, where I've ordered from many, many times. Most of my cameras and lenses have come from there. In fact, the last camera I bought only came from somewhere else (Amazon) because it was not in stock at B&H and I wanted it "now." B&H is not the cheapest place, but their prices are good and they are quite reputable. I've walked past their B&M location a couple times, but never been inside because it's always been a Saturday and they were closed.