A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?
If you accept randomized algorithms you could use TREAP. This data structure is BST where each node is augmented with priority, a random number. The only one invariant over normal normal BST is that parent's priority must be greater than children's. This results in a very simple implementation of Insert and Delete functions (recursive variant is 10-15 lines of clean C code).
The complexity of basic operations is $O(\log N)$ on average.
It is possible to cut-off all nodes below threshold in $O(\log n)$ time assuming that nodes below the threshold are not disposed.
Node cut(Node node, int threshold) {
   if (node-&gt;key &lt; threshold) {
      // optionally dispose node, and subtree at node-&gt;left
      return cut(node-&gt;right, threshold);
   }
   node-&gt;left = cut(node-&gt;left, threshold);
   return node;
}

root = cut(root, threshold);

Note, that there is no rebalancing because the node is replaced by one of its children (or subchildren). As result the priority invariant in satisfied.
Disposal of nodes with a key below the threshold will increase complexity to $O(k + \log n)$, where $k$ is a number of disposed nodes.
Cost of disposal will be amortized to $O(1)$ over multiple operations because each node is created and disposed only once.
Removal of nodes above a given threshold will require symmetrical functions.