Here is a case where the non-exhaustion of the budget can happen without it being preference-driven.
Assuming totally standard preferences, the budget most likely won't be fully consumed if we have some degree of indivisibility in goods. Note that the resulting "gaps" in the set of feasible consumption bundles has nothing to do with preferences: we assume that the consumer can order etc all conceivable consumption bundles, even those that are not available to him.
Note that by postulating the existence of a single price per good we unavoidably assume a single unit of measurement for the good. This allows us to reduce the divergence to the neighborhood integers.
If $(x^*, y^*)$ is the optimal bundle and (under standard preferences) $p_xx^* + p_yy^* = M$ then the candidate expenditure will be
$$E_1 = p_x\lfloor\tilde x\rfloor + p_y \lfloor\tilde y\rfloor < M $$
$$E_2 = p_x\lfloor\tilde x\rfloor + p_y \lceil\tilde y\rceil $$
$$E_3 = p_x\lceil\tilde x\rceil + p_y \lfloor\tilde y\rfloor $$
$E_1$ is certainly smaller than the budget, while $E2$ and $E3$ may be larger equal or smaller, depending on how big are the prices. If either $E1$ or $E2$ are within budget, they certainly dominate $E_1$ in terms of utility (given standard preferences and assuming both are goods and not bads), so one of them will be observed if they are feasible, while if both are feasibe, the one providing greater utility will be observed. Otherwise $E_1$ will be observed.
If one thinks that this is some artificial situation, with negligible deviation, it is not: it is one of the main drives behind the observed variety in packaging the same good (and a trend towards smaller packages), which is an attempt to reduce the degree of indivisibility and cover some of the gaps in the feasible consumption bundles set. Essentially by reducing the implied physical quantity that corresponds to "one unit", we lower the corresponding prices, and so make deviations from the optimal bundle $(x^*, y^*)$ smaller.