That said, I think people worry too much about credit histories. And every foreigner I've met who moved to the US as a pharma scientist with a 6 figure salary has been able to get a mortgage despite not having a credit history in the US. A good credit history (vs. having none) generally seems to matter when you are getting a mortgage close to the limit given your salary.
A very low credit score doesn't stop me renting an apartment either, probably for similar reasons. Although it did mean I couldn't rent in the presidio
In my experience, I've had to cancel one credit card and one debit card due to fraudulent charges. With the debit card, you're right, some money did disappear for a few days, but the bank put it back as soon as we signed and notarized a form.
For the credit card, they dropped the charges right away without me ever paying for it, but the merchant (ebay) sent my info to a collections agency, so it ended up being more of a hassle then the stolen debit card.
They traced the debit card theft back to a string of thefts at a department store we had shopped at (presumably one particular employee), but we now use cash for essentially all shopping, so that isn't a risk anymore. (Although I do try to watch out for card skimmers on ATMs.)
But, when I said I pay my bills on time, I actually meant that my bank pays my bills on time. All of my regular bills are paid automatically through my bank.
For travel, airfare and hotels do go on credit cards, but more often then not, we drive and stay with family or friends. (Excluding work travel... but my job pays for that.)