Bad Performance /category/postname permalink?

(1) How bad is using category/postname for permalinks?

I’ve read that using the category/postname or tag/postname or even the postname/ permalink is terrible for server performance. I’ve read about I’ve read all the recommendations about using numbers at the beginning of permalinks (year/month/postname) because it’s easier to match numbers than posts, especially if of a certain sequence. Supposedly much easier on the server for URL rewriting, got it.

But here’s my problem. There is no way I can use an ad server for categories unless a category or tag is in the URL. The alternative is to then use a plugin which determines the category and serves ads for that category, causing even more overhead and work for the server. So I’d prefer to have my URLs be:

/cars/myarticle-postname-here/
/buildings/myarticle-postname/

(2) Using a plugin or tag to handle permalinks

Next is which to use. Nested categories are killing me. I just want cars, trucks, bikes, buildings etc. – whatever is the main category area. Subcategories like cars/audi and cars/porsche are great for the user to navigate but completely unnecessary in the URL. cars/postname is fine. There are two solutions I can see:

1) /tag/postname/ in the permalink. You have to hack in the code to make it work even though this solution is in the codex. Apparently it was left out in version 3.0 by accident I think.

2) Use an amazing plugin that works so well.

http://wordpress.org/extend/plugins/search.php?q=scategory&sort=

These work incredibly well and it would make sense if you could just set the permalink for each category to be what you want it to be like this is! I worry about (a) server load, and (b) potential incompatibility.

Thoughts anyone?