My friends girl tried to rent from Redbox with a Visa Gift Card once and it declined it. This is more than likely because you can't be tracked with a Gift Card, since they require no personal information to be used and thus they can't charge you for never returning the video.