Do I have a story to tell. I ended up going with Hertz. My first stop was Enterprise and I had my car picked out and everything. I pull out the payment, my Visa check card and was told they could not accept that. They requested I either A) Use a major credit card or B) have a "co-signer" come in with a major credit card and they could assign me as a co-driver (more money). I have a major credit card BUT Enterprise told me they would take up to of $600 out for a deposit on top of my rental fees. Only person who could cover that was my Grandma and we called her. Guess what, she doesn't drive (over 80yo) so she couldn't be used as a driver on the contract which made her CC worthless. The next step was to have TWO utility bills that show a flawless record for 6 months. My mom could cover this and had a Visa check card but we would have to run home for her bills as they needed statements, not the bills that she had with her that day to mail in. Home being 20 minutes away this was not worth it. I found out they would also take out the $600 deposit out of my check card and I couldn't take that kind of hit with my vacation. At this point I was so mad we just left. Their web site doesn't say anything about not accepting check cards and even the counter witch said this and smiled as she said "Sorry, but we don't trust check cards, Visa or not. Sorry our web site doesn't state this."
I went to Hertz afterwards to check on what they could do. Prices are a little higher but I drove off the lot with a car in under 15 minutes after using my check card and only a $100 deposit. Counter guy was very nice and we even BS'd a little bit.