making a texture bigger then the screen solution is okay cause scaling down provide still a good quality
and if you have not much of this big images it would also render nice on youre laptop

Or should I use a 512x512 resolution for my game...and strech it to 640x480 ... but that would look really bad no?
yeah never do this, stick to normal screen solutions, its also helpful if you use fullscreen