everything shows up in a database called the 'national crime information center'.
http://www.fas.org/irp/agency/doj/fbi/is/ncic.htm
your federal investigators have access to it, but a civilian employer, for example, does not. anything federal, and you can bet it will be tapped. expunged records show up as whatever the initial conviction was, 'pre-expunged', and then 'expunged'. even if you've been arrested, and not charged, the arrest still shows up in the database. juvenile records show up. therefore, it is always, always in your best interest to disclose anything and everything that may be in your past. in not doing so, should your recruiter and/or investigators find out about them on his/her own, this will point to lack of character and integrity on your part-- something that the military is definitely not seeking.
living overseas shouldn't be a problem, depending on what you did when you were there, and who your references are. i have friends who have spent decades in communist/fascist countries, and while their clearances took a little longer, they were still cleared. (oh, and some of them were also fairly serious drug users when they were in high school.)