My implementation of a memmem() like function
I'm trying to rewrite it from scratch. How does this look?

Mis-matched function signature
OP code uses
void *MemContainsMem(const void *StrStart, register unsigned long StrLen, 
    const char *Substr, register const unsigned char SubstrLen);

The referenced code uses
void *memmem(const void *haystack, size_t haystacklen, 
    const void *needle, size_t needlelen);

Recommend to use the same function signature.  Unclear why OP changed from size_t to unsigned long and changed pointer type.
Use of Str... hints at a string, yet this function does not operate on strings.  Maybe Mem...?  Hard to beat the names needle/haystack.
Invalid access in corner case
The first *Substr in memchr(StrStart, *Substr, StrLen); is UB when SubstrLen is 0.
Code should gracefully and correctly  handle SubstrLen == 0 and SubLen == 0 cases.
register
register is a good keyword to use when the rare programmer better understands the compilation situation better than the compiler.  For the other 99.99% of us, drop register and let the compiler do its job.  Do not tie the hands of the compiler.
0 vs. NULL
Minor: Since the return type is a pointer, consider returning NULL rather than 0 as being more idiomatic.  Either works.
Unneeded code
The first if (StrLen &lt; SubstrLen) { return 0;  appears unnecessary as that case is detected in later code.
Redundant test
} while (Str); can be replaced with } while (1);.  Alternatively make loop a while()
//register const unsigned char *Str = memchr(StrStart, *Substr, StrLen);
//do {
//    if (!Str || StrLen &lt; SubstrLen) {
//        return 0;
//    }

const unsigned char *Str;
while ((Str = memchr(StrStart, *Substr, StrLen)) != NULL &amp;&amp; (StrLen &gt;= SubstrLen)) {

Invalid pointer subtraction
Not portable to subtract void * in NewStr-Str.  Use unsigned char *NewStr instead.
Array or string
The define treats Substr as an array and not a string.
Good macro practice uses a () arround each parmeter.
// #define MemContainsStr(Str, StrLen, Substr) \
//    MemContainsMem(Str, StrLen, SubStr, sizeof(SubStr))

#define MemContainsStr(Str, StrLen, Substr) \
    MemContainsMem((Str), (StrLen), (SubStr), strlen(SubStr))

Be wary now of double evaluation of SubStr


Are there register variables that shouldn't be, how can I further optimize this code?

I recommend to drop all register usages and simple enable greater compiler optimizations levels.
A fundamental weakness to this code is that it is O(m*n) where m, n are the lengths of the needle and haystack.
Better algorithms are O(m+n) and oblige significant code changes.

ToDo
Bug??
Str+1 is suspicious in NewStr = memchr(Str+1, *Substr, StrLen); as it is not clear that StrLen &gt; 0 always at this point.  e.g. StrLen, SubstrLen both are 0.
Hmmm