Looks like Memo was somewhat broken by the latest hard fork. Transactions started broadcasting with less than 1 sat/byte fees and it looks like some other weirdness is happening. Hope they get it fix.
To be clear, transactions were always being broadcast with less than 1 sat/b fees - the change was that miners stopped mining these after the fork.