Оборот почти что употребляется, фиксируется словарями, но нужно учитывать, что он имеет разговорную стилистическую окраску.
Корректно: В России больны ВИЧ почти миллион человек.
Согласны с Вами, слово почти во втором предложении неуместно, следовало бы использовать слово около.
Первый вариант лучше, поскольку второй может быть прочитан как "почти... в городе".
Да, корректно с тире: Почти сразу — дырки на подмышках...
Нет, такое употребление некорректно. Почти – 'так, что немного недостаёт до чего-либо'. О 72 %, 73 % можно было бы сказать «почти три четверти», но 76 % – это уже больше, чем три четверти.
Следует писать раздельно: спустились в почти не освещенное помещение, заставленное стеллажами и коробками.
Лучше изменить способ подачи числовой информации: Город пополнился почти восемью с половиной тысячами новых жителей. Если все же необходимо оставить числовую форму, то правильно: Город пополнился почти 8,5 тысячи новых жителей.
Такое употребление не является точным. Практически значит "по существу, по сути дела". Конечно, сегодня это слово обрастает этим "приблизительным", "примерным" значением - "почти".