I cannot help you with the answer, but perhaps the question...
The annealing temp is based on the number and type of bond between base pairs - so getting exactly 44C is going to be tricky with degeneracy, if not impossible. This is probably why it didn't make sense to code it into primer3. Also, just in general, 44 is pretty low. I will be surprised if your specific primers are really specific at that temp.
The number of variations will be based on the number of degerate bases you use as your primer sequence. Are you saying that this is totally variable and you dont care what regions of genome you target? If thats the case, its going to be up to the number of degenerate base pairs you put in... to get 256 you'll need 4 degerate nucleotides.
I think point 4 means that you want to make sure this super primer also doesn't bind to a certain region?
To beat this puzzle, I would do the following:
You want an annealing temp of 44, so you're going to need roughly 14 to 15 nucleotides on this primer.
4 are already going to be used by the degenerate bp.
Stick them all on one end of the primer, and solve the simpler question of what 10bp sequence targets the mouse genome with a 1/3000 binding frequency.
Maybe try BLAT instead of BLAST and use GNU parallel to speed up the searches?