I've been to the Amazon Brazilian BBQ in Shekou once and once in GouWuGongYuan, and it was pretty good. You can eat unlimited BBQ food and get lots of icecream etc. Not all BBQ food was equally good, but overall a good experience and not too expensive! You can eat a lot and will be very full :)

At the Coco Park branch, you can sit outside or inside.

AmsterdamSnack: Dutch delicacies in Shenzhen!  I was totally amazed to see this place in Dong Men. I think it opened around October 2009, hope they stay for a while so we can all enjoy 'kroketten' in Shenzhen :)

Update: we've now been to AmsterdamSnack to try the kroketten and patat (french fries). See for new photos below: 

Inside the Central Walk shopping mall in Futian district, there is a small food market where you can eat lots of different kinds of food for affordable prices: Korean,Western, Japanese, Chinese.

Address:

Central Walk shopping mall in Futian

When you enter from the side of the Exhibition Hall, go down one level and then left immediately and you will see it soon on the outside (not the inner area).

Coco Park food court is located at the 3rd floor of Coco park. It's similar to the food court in Central Walk in setup; both offer tepanyaki (Japanese style food fried on a hot metal plate) and various other Chinese cuisines. You normally buy a card to store some money and then pay at the various little counters with this card. Currently (June 2009) they offer a special offer: buy 300, get 330Y worth of deposit. The little shops often have special discounts, such as Korean-style stown-bowl rice for 18Y (instead of 28) and tepanyaki fried beef for 28Y instead of 48Y. There is also an excellent fresh juice bar that offers really nice drinks. So far the most amazing combination has been pineapple+haw, delicious!

Address:

Coco Park (Gou Wu Gong Yuan subway stop), 3rd floor above the main entrance / side of the Jusco supermarket.

website: delicity.com.cn  

ColdStone Creamery offers a nice variety of ice cream from classics like French Vanilla and Chocolate to unique flavors like Cake Batter and Cheesecake. You can get your favorite flavor ice creams and add in a topping like Reeses Peanut Butter cups which they will mix in for you on a marble counter and serve it to you in a nice specially made waffle cone/cup. They also have a wide variety of suggested specials like Monkey Bites and things like milkshakes. Prices for ice cream are a bit up there ranging from about 20-40RMB depending on the size.

Address:

Guomao metro. Use the exit for Kingglory Plaza and as soon as you get in to the mall, it is on your right side next to a Watsons

Focaccino received some mixed reviews, but mostly positive at ShenzhenStuff, but overall seems to be a good place for vegetarian cuisine.

•  nice selection for vegetarians. its a bit expensive, but the set lunch is a good deal...for about 35RMB (i think) you get a drink, soup, bread, main dish, and small dessert. great bargain! friendly staff and nice to have the wifi as well.

Address:

Coco Park (Shopping Mall Exit C), Fuhua 3 Road, Futian

福田区福华三路星河Coco Park (购物公园站)酒吧街088,089号铺

(0755) 2531-3781

"Four seas international house" (四海一家 ). I've been to this restaurant once and it's great fun. It's not cheap by Chinese standards (around 150RMB/pp), but you can eat as much as you want for a fixed price and all food is displayed so you don't have any problems with translations and even better: there is a big variety of food from different parts of the globe. So no matter if you want to try Chinese, Japanese, Indian or Italian, it's all possible. Seafood, cake, fresh fruit juice. All possible! It's on the 3rd floor of Yitian Holiday Plaza and the price varies according to the time of the day and day of the week, with weekend evenings the most expensive.

Address:

Inside Yitian Holiday Plaza in Nanshan district, across the road from Window of the World. You can take the subway directly to Yitian holiday plaza.

Garwon (also known as JW) is a Cantonese chain of restaurants. Food is clean and prices are low to normal. Not the place to go if you want to eat spicy food or enjoy a nice dinner, but perfect for midday lunches at work or when you are shopping. Personally I eat almost every day at JW because it is located close to my work in the science park in Nanshan district. They also deliver via their website .

Mezzo is a high-end Italian restaurant in the Sheraton hotel in Futian district. Read this review by ShenzhenDaily:

• An Italian banquet at MEZZO starts with a variety of appetizers. A good choice is the selection of four appetizers (150 yuan, US$21), which is a combination of four popular Italian salads. The toasted Italian bread topped with sautéed cherry tomatoes (100 yuan) and the Parma ham with marinated melon and seasonal fruits (130 yuan) are also recommended to stimulate the taste buds.
  

Jollibee is a popular Filipino fast food burger chain. Jollibee Shenzhen is located in Luohu district.

Address: 

The location of this store is in Luohu in the front square of the Carianna Center. This is located midway between the Guomao subway station and the Luohu subway station.

La belle Epoque is a high-end French restaurant located  in MixC in Luohu. The chef is a native Frenchman and the decor is very beautiful. I have eaten there once and the quality was very good. Highly recommended for authentic French food. They also offer special lunch-time sets.

Address:

No. 299 Store, The MixC at City Crossing, 1881 Baoan Road S., Luohu District Telephone: (0755) 8266-8880

SZDaily wrote about the restaurant "Martin Yan’s cooking school" in May 2008. This is both a training centre for chefs who want to learn Chinese cooking, as well as a restaurant.The center organizes culinary tours for both chefs and lovers of Chinese cuisine, taking them to popular destinations like Guilin, Xi'an and Beijing.

• The training center takes up the entire second floor of the building. With a floor area of more than 2,000 square meters, it features work stations, a chef's table and multi-media equipment. It can accomodate up to 32 trainees at a time, and also an audience of about 80 [...] The signature set meal of five courses (108 yuan, or US$15.56 per person) is a popular choice. The crispy rice with assorted seafood cooked in supreme oyster sauce is served piping hot in a pot. The seafood compliments the flavor of the dish very well.
  

Address:

Chef Martin Yan Culinary Arts Center, No.5 European-style Street, Window of the World, Nanshan District (南山区华侨城世界之窗欧风街5号楼甄文达大师厨艺中心)

Located on the first floor of the building is a branch of Yan's SensAsian restaurant chain.

McDonalds has over 60 stores in Shenzhen so you don't really need to look far to find one. Sizes are smaller than in the USA (I think a good thing) and it's most often quite busy in McDonalds. There are very few drive-thru's (I believe they are experimenting in Shanghai with this concept), but there are quite a lot 24/7 stores and even some McDonalds that deliver food to your home. Don't forget McDonalds always has discount tickets on their website which you can print out (b/w of course) and enjoy a few yuan discount.

Address:

Everywhere: McDonalds restaurants list (in Chinese)

Milano Italian Restaurant is a real Italian restaurant in Shenzhen which run by 3 Italians in Futian district. ShenzhenDaily wrote a review about Milano.

• A cozy place for an exotic dinner with your loved one, or a casual family reunion, or even a corporate meeting, Milano offers the finest Italian dining experience at affordable prices, with a single dinner costing around 150 yuan.With more than 80 percent of the ingredients flown in from Italy, the Italian chefs use the freshest available ingredients to create authentic Italian flavors and bring the real taste of Italy to Shenzhen palates.

ShenzhenParty also wrote a review about them, which you can read here . I have not been to the restaurant (too expensive for me), but they were very enthusiastic about it:

• It is needless to say that we were utterly satisfied by the meal, but what stole the evening was the Tiramisu, it was simply put the best Tiramisu this side of the Vatican, not the gooey glop you get around the world. It left us speechless and asking for more and more.I told the owners and Chefs that I will send back as many people as I can to this gem of a place. So my fellow Shengers, build up your appetite and head to Milano’s. Bon Appetito’s

Address: 

1/F, Chuangzhan Center, Ahhui Building, NO.6007 Shennan Road, Futian District, Shenzhen.

Tel:83581661
深圳市福田区深南大道6007号安徽大厦创展中心首层

You can call owner Giulio at 13509628146 for reservation.

Papa John's has several restaurants in Shenzhen, but no online ordering yet. All addresses should be correct as of Januari 2009:

Addresses:

Futian:

• south/fumin no. 106 gao fa chen chi fumin road  - phone 8675583809492
• south/huaqiangbei 3rd floor manhar shopping plaza huaqiangbei road - phone 0755-83272820
• south/citic city plaza international street middle shennan road - 0755-25943778

Nanshan:

• south/poly unit a1-14 1st floor poly culture center nanshan business & culture center - telephone ?
• chuangye store 1st floor, poly garden business centre nanhai road - phone 8675526428803
• south/coastal city unit 149 1st floor costal city shopping mall nanshan business & cultural center - phone 0755-86359959

Luohu:

• south/bao'an nan 1st floor hubei baofeng bld # 1054 boa'an nan rd - telephone 0755-25561187
• south/dongmen 2nd floor, luohu cultural center dongmen renminbei road - phone 8675582175450

Prince Kitchen Creative Cuisine 王子厨房

Customer review:

• Decoration is nice at Prince Kitchen but kinda dark, food is ok if i would rate it from 1-5 it probably like around a 3.5
  but i think most people go there for the atmosphere
  

Address:

5/F, Citic City Plaza, 1093 Shennan Zhonglu.

深南中路1093号中信广场5层. 2598-8333

Royal Palace Bar & Family Indian Restaurant

Address:

No. 1118, Yan He Raod, Horaton Hotel, Ground Floor, Shenzhen 86-755-82347166

Saizeriya opened its first Italian Restaurant in april 2009 in Dong Men (Luohu district) in Shenzhen. After talking to one of the waitresses, we found out that  Saizeriya already has several branches in Guangzhou and it is very popular there.  After eating in the restaurant the 11th of April, we fully understand why. Saizeriya tastes good and is very cheap. Forget about Pizza Hut or Spaghetti House, this is the new place to be!

The food arrived quick to our table and everything tasted fresh and was very hot. We only spend 66 yuan for 2x salad (2x8Y), 1x seafood doria (10Y), 1x spaghetti (9Y), spicy sausages (12Y), 1x cheese cake (10Y) and 1x icecream with fruit (9Y) . Great restaurant, highly recommended.

Shekou is the southern part of Nanshan district. The area by itself is quite large and famous for it's foreign community. The center is quite small, but contains some places of interest such as a big boat that has been converted to hotel&restaurant. In the area opposing the boat many foreign restaurants can be found such as French Kiss, Indian food, Thai food and so on. Also several bars in this area.

Personally I think that the two stores that sell imported foods are more interesting. They are located a bit to the south from the restaurant area, close to a big sign for a school. It's within walking distance, just follow the big road.

If you want - or need - to take a break from Chinese food, you will definately find something to your liking here. The prices are also much higher than Chinese restaurants though. There is also a Sub-Way restaurant with good sandwitches.

If you take the bus further to the south, you will arrive at Shekou ferry terminal. From here boats go to Hong Kong International Airport, Hong Kong Island,  Macau and Zhuhai.

Address:

Tianjun Mansion (next to Panglin Hotel), First Floor, Dongmen South Road (0755) 8220-2129

Street food is very popular in China, especially for young people (because it is cheap). For a few yuan you can eat noodle while you sit down on mini plastic chairs next to the road. It's also very popular to get bbq squid or other meat on a stick. I've started to collect some pictures about this. See more photos below: