Are you sure you are using the correct size seatpost? You can increase the width depth of the slot in the back of the frame where the seat post goes in to make it easier to tighten the seatpost more firmly.
seat tube slot:
The play between seatpost and frame should be just barely noticable when wiggling the seat post back and forth without the bolt clamped down.
If the play between seat post and frame is quite substantial you could consider using a piece of beer can (or other similar material) as a spacer, but this is not a very elegant solution.
You could try using some sandpaper on the inside of the seat tube to make it rougher/ make it harder for the seat post to rotate out of position.
Is the problem that the seat post clamp bolt loosens up by itself? or will the seatpost rotate/move even when the seatpost bolt is tight?
If the bolt loosens up then I would suggest using locktite or another similar threadlocker, I don't believe anti-seize has thread locking properties but I could be wrong on this. Also make sure the currently installed seat post clamp is the correct size for the frame/seatpost.
When using non-carbon frame and seatpost you shouldn't worry too much about overtorquing in my experience. As long as you don't strip the head of the bolt(s) or threads of the clamp there should be no issue. 5-9Nm should suffice according to the following website: http://www.bike-manual.com/brands/trek/om/cross/torque_spec.htm but if you make sure your bolt can handle it without stripping/ruining the bolt head you can go a bit higher if needed.
On 1 bike I had a a seatpost which had the same issues as you describe, I thought the clamping was the issue but as it turns out the top piece of the seat tube (which clamps to the seat itself) was rotating inside the tube-part of the seat tube. Unlikely that this is the case for you since you ordered a new seatpost though.