My car is evil

So I got the starter off, and the new one on. it started all nice nice and so i drove it to work (i do deliveries) and so i go to the first house and i turn off the car bring em the package and go to start the car again....and nothing....after calling a tow truck (which never came) and waiting for an hour i get back in and say wha!? it starts... so i go to my other job and it starts again later that night...this morning i start it, go to do deliveries and today i took the company car, finished, got lunch and got a call from my boss to do one last delivery, i say what the hell i go there turn the car off get the package and go to start my car instead of the company car.....doesnt start...has been there all afternoon and it still wont start...with a brand new starter!? i think it has something to do with the engine being hot or something....any help or ideas?

Do you have more than one key you can try?

Does it crank?
What year is the car?
Older vw's (93-99) had problems with ignition switches and the contacts internally where the car would not start or crank.

Also, check the connections at the starter.. they may be loose