No, items are not completely random. I believe they are mostly based on your moves (like if you have 4 special moves it might give you Choice Specs etc.).
EDIT: Just got a Hypno with Belly Drum and no physical moves. I'm pretty sure that's not supposed to happen :/
If you get the feeling of being watched in darkness when nobody is around, Hawntah is there.