> you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number.

In general, this is a dumb trade to make, because more key bits are cheap and that computation costs every user.

Things like what you describe exist-- where initial key scheduling does key stretching, etc.

> Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive

Anything is possible, but this often does more to hurt low-resource users than brute force also.