Update: I've now found two solutions that require only $25$ weighings:
$$
01011011100010111101000001100111110011010100011010\;,\\
00101110001101001010111110001000110010011111011101\;.
$$
These are the only solutions known (in the context of this post) with $k=n\,/\,2$, for any $n$. I found them using Tad's recipe of repeatedly maximizing the determinant of $AA^\top$ by hill climbing and testing the candidate with the highest determinant among several runs. The determinants are
$$
87546852131623099566361867104\;,\\
93001686149176479553585114299\;.
$$
I only had to test half a dozen candidates to find these two solutions, which seems consistent with $f(50)\simeq 22.4$. I'll now be testing these two with $24$ weighings; that will take the better part of a day and will require a bit more than a trillion difference vectors to be checked in each case.
I believe the bounty should go to Tad, who developed the mathematical approach. I tried to improve on it but couldn't, so instead I coded it a whole lot faster :-). Here's the code. It uses a special bit encoding for efficient arithmetic with vectors over $\mathbb F_3$. On my MacBook, it takes half a minute to test a candidate with $31$ weighings and two hours for a candidate with $26$ weighings.
The best solution it's found so far is $01010111100010011111110000111011000101101100100001$, with $26$ weighings required. I'm now looking for solutions with $25$ weighings, but that requires up to six hours of testing per candidate. I expect the minimum to be near $23$ (see below). I haven't implemented Tad's determinant maximization approach yet; the above solution was just the third candidate I tried with uniform sampling among the vectors (uniform sampling among the rotational equivalence classes would be worse since it gives higher weight to periodic sequences).
Here's a short summary of the mathematical basis of the code, mostly following Tad's ideas and notation; $n$ is the number of coins, and $k$ is the number of weighings. We can treat the two weights of the coins as $0$ and $1$. Then every possible weight configuration is characterized by a binary weight vector, and the differences between weight vectors are ternary vectors with entries $-1$, $0$ and $+1$. A solution is admissible if the $k\times n$ matrix $A$, with entries $A_{ij}\in\{0,1\}$ according as coin $j$ is weighed in weighing $i$, has different products with all possible weight vectors, or equivalently, if its product with all possible difference vectors is non-zero.
We can regard the difference vectors as vectors over $\mathbb F_3$. Only the difference vectors in the kernel of $A$ over $\mathbb F_3$ can be in the kernel of $A$ over $\mathbb Z$. The kernel over $\mathbb F_3$ will generally contain $3^{n-k}$ difference vectors, and these we have to check over $\mathbb Z$ (actually only half of them, due to invariance under negation). The key to doing this efficiently is to bit-encode $\mathbb F_3$ such that the time-limiting steps (addition, componentwise multiplication and summation of vectors) can be performed compactly using integer operations and table lookups instead of iterating over $n$ vector components.
Here are some results that expand on Tad's results for values well below $50$. $n_\text{c}$ is the number of equivalence classes under rotation; the numbers in the header row are $n-k$, and the numbers in the bodies of the two tables are the numbers and fractions, respectively, of rotational equivalence classes that yield a solution.
\begin{array}{c|c|cc}
n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline
2&1&1\\
3&2&1\\
4&3&2\\
6&4&2&1\\
8&5&6&3\\
14&6&6&4\\
20&7&18&12\\
36&8&20&17&8\\
60&9&50&45&25&6\\
108&10&74&71&56&17\\
188&11&186&178&130&83&4\\
352&12&216&214&200&135&42\\
632&13&630&614&520&469&261&6\\
1182&14&916&910&878&787&535&101\\
2192&15&2002&1988&1924&1831&1427&648&22\\
4116&16&3040&3037&3000&2926&2605&1686&330&2\\
7712&17&7710&7699&7464&7330&6915&5361&2131&34\\
14602&18&10806&10801&10760&10649&10310&9014&5547&875\\
27596&19&27594&27582&27270&27110&26565&24773&18964&7307&152\\
52488&20&40642&40639&40592&40474&40024&38487&33414&20254&3102&2\\
99880&21&94658&94640&94440&94281&93518&91759&85546&65010&24368&508\\
\end{array}
\begin{array}{c|c|cc}
n_\text{c}&n&0&1&2&3&4&5&6&7&8&9\\\hline
2&1&.5000\\
3&2&.3333\\
4&3&.5000\\
6&4&.3333&.1667\\
8&5&.7500&.3750\\
14&6&.4286&.2857\\
20&7&.9000&.6000\\
36&8&.5556&.4722&.2222\\
60&9&.8333&.7500&.4167&.1000\\
108&10&.6852&.6574&.5185&.1574\\
188&11&.9894&.9468&.6915&.4415&.0213\\
352&12&.6136&.6080&.5682&.3835&.1193\\
632&13&.9968&.9715&.8228&.7421&.4130&.0095\\
1182&14&.7750&.7699&.7428&.6658&.4526&.0854\\
2192&15&.9133&.9069&.8777&.8353&.6510&.2956&.0100\\
4116&16&.7386&.7379&.7289&.7109&.6329&.4096&.0802&.0005\\
7712&17&.9997&.9983&.9678&.9505&.8967&.6952&.2763&.0044\\
14602&18&.7400&.7397&.7369&.7293&.7061&.6173&.3799&.0599\\
27596&19&.9999&.9995&.9882&.9824&.9626&.8977&.6872&.2648&.0055\\
52488&20&.7743&.7743&.7734&.7711&.7625&.7333&.6366&.3859&.0591&.0000\\
99880&21&.9477&.9475&.9455&.9439&.9363&.9187&.8565&.6509&.2440&.0051\\
\end{array}
Here are the minimal $k$ values up to $n=26$ (denoted by $f(n)$ as in Tad's table), together with the numbers and fractions of solution classes at minimal $k$:
\begin{array}{c|c|c|c}
n&f(n)&\#&\#\,/\,n_\text{c}\\\hline
1&1&1&.5000\\
2&2&1&.3333\\
3&3&2&.5000\\
4&3&1&.1667\\
5&4&3&.3750\\
6&5&4&.2857\\
7&6&12&.6000\\
8&6&8&.2222\\
9&6&6&.1000\\
10&7&17&.1574\\
11&7&4&.0213\\
12&8&42&.1193\\
13&8&6&.0095\\
14&9&101&.0854\\
15&9&22&.0100\\
16&9&2&.0005\\
17&10&34&.0044\\
18&11&875&.0599\\
19&11&152&.0055\\
20&11&2&.0000\\
21&12&508&.0051\\
22&12&8&.0000\\
23&13&2340&.0064\\
24&13&36&.0001\\
25&14&10688&.0080\\
26&14&216&.0001
\end{array}
The solution class counts of $2$ for $n=16$ and $n=20$ that both come at the end of an unusual triple of identical values of $f(n)$ are salient; here are the solution vectors:
$$
0000101110111011\;,\\
0000110111011101\;,\\
00000101111011110111\;,\\
00000111011110111101\;.\\
$$
Note that in both cases the two solutions are related by inversion, they contain slightly longer runs of $0$s than of $1$s, and the runs of $1$s are separate by single zeros.
It's tempting to speculate that the bound $f(n)\gt n/2$ that holds up to $n=26$ will continue to hold for higher $n$. However, I don't believe that this is the case. There's already a slight indication of this in the data; the solutions are gradually encroaching on the bound. (The trends in the absolute numbers are relevant here, not in the fractions, since we only need a single solution.) The fact that the third uniformly randomly guessed candidate turned out to be a solution for $k=26$, $n=50$ also points in this direction, since it suggests that the density of solutions at that point is much higher than it is for $k=n/2-1$ at lower $n$ values (where it's almost negligible).
Moreover, statistical considerations suggest that the asymptotic behaviour of $k$ might be $n\,/\log n$. There are various handwaving arguments that could be used to support this, based on entropy or collision probabilities; the details may be hard to get right, but the bigger picture is the same in each case: The $k$ measurements each have an effective space of order some power $n^\alpha$ to spread across ($\sqrt n$ if we consider them to be binomially distributed), so our discerning ability grows with $n^{\alpha k}$, while the number of possibilities we need to be able to discern grows with $2^n$; equating the logarithms yields $\alpha k\log n=n\log2$ and thus $k\propto n\,/\log n$.
Such $n\,/\log n$ behaviour seems consistent with the data up to $n=26$, so we can get a rough estimate e.g. from $f(26)=14$:
$$f(50)\simeq\frac{50\log26}{26\log50}\,f(26)\simeq1.6\,f(26)\simeq22.4\;.$$
That leaves ample space for improvement. :-)
Best Answer
You can do better than 68 + 67 on the first weighing! Try 57 + 56 + 22. Take one marble from each of the 56, and two marbles from each of the 22. Then, the scales show either "Error", or "999" or "998". If it shows "error", all 100 marbles on the scales are real, and the hollow marbles are among the 57. If it shows "999", the hollow marbles are among the 56, and if it shows "998", the hollow marbles are among the 22. I will assume worst case in the rest of the explanation, so let's say there are 57 boxes left to examine.
(If the scales say "999" rather than "error" if there are more than 999 grams worth of marbles on it, you will have to do 57 + 57 + 21 instead. This doesn't affect the rest of the algorithm.)
The 57 can be divided further into five groups of 14 + 14 + 14 + 14 + 1. Take one marble from each box in one of the 14-groups, two from each the second 14-group, three from each in the third 14-group, and four from the lone box (leaving the fourth 14-group untouched in this round). See whether the scales really show 844, and if not, how many grams are missing.
Worst case, you have 14 boxes left after the second weighing. You can now take one marble from box 1, two from box 2, and so on, leaving one box unused. If all marbles on the scales are whole, the scales will show 910, and the unused box will have hollow marbles. If not, count how many grams are missing, and that will identify the box with the hollow marbles.
This totals three weighings. I do not know that this is the best you can do, but I'll be very impressed if anyone comes up with a way to do it in 2.