We provide a construction of sets of d/2 + 1 mutually unbiased bases (MUBs) in dimensions d = 4, 8 using maximal commuting classes of Pauli operators. We show that these incomplete sets cannot be extended further using the operators of the Pauli group. Moreover, specific examples of sets of MUBs obtained using our construction are shown to be strongly unextendible; that is, there does not exist another vector that is unbiased with respect to the elements in the set. We conjecture the existence of such unextendible sets in higher dimensions d = 2n(n > 3) as well. Furthermore, we note an interesting connection between these unextendible sets and state-independent proofs of the Kochen-Specker Theorem for two-qubit systems. Our construction also leads to a proof of the tightness of a H2 entropic uncertainty relation for any set of three MUBs constructed from Pauli classes in d = 4. © Rinton Press.