Having a upper bound is probably good enough for me. The upper bound is the nearest power of 2, right?
I think the Merkle path to the last transaction would give you the number of txids. You could prove that it is the last by making sure that hashes are doubled.
You can work out which levels of the tree have an odd number of entries, and so has to double up the last hash.
As a related question, in the current protocol, could an SPV node requests for the x-th transaction in the y-th block, without knowing the txid of the transaction?
The merkleblock packet could be used as a response. I don't think there is is a way to request a particular indexed transaction though.
Indexed lookups would be good though. Parallel download would be easier if you could ask for the 100,000th block rather than having to download the first 99,999 blocks. In almost all cases all peers would agree, so there is no risk. Headers first makes this less of an issue though.