As was pointed out, Tuesday isn't always street date. Disney is notorious for releasing movies on Thursdays and Fridays. As far as movies go, the bigger retailers will have those in the back up to a week before street date.
I don't remember fines associated with street date violations, but I know that smaller retailers that violated street date would have future shipments sent to arrive on street date (allegedly to prevent them from putting it out early again). Bigger retailers (Target, Wal-Mart, etc) can get away with street date violations because they wield so much financial power over the distributors and producers.