Deterministic encryption for a limited space: using HMAC as IV
Let L be your constant data length, choose a non-negative integer $\sigma$, choose a

FPE scheme over strings of length $\sigma$+L, and have $s$ range over strings of length $\sigma$.

encrypt$\hspace{-0.02 in}\big(\hspace{-0.04 in}\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle ,\hspace{-0.02 in}m\hspace{-0.03 in}\big) \;\;\;\; = \;\;\;\; $ FPenc ( ​ k ​ , ​ s || m ​ )

Decryption of c with $\langle k\hspace{.02 in},\hspace{-0.03 in}s\rangle$ is as follows:

if ​ length(c) ≠ $\sigma$+L ​ then output $\bot$, else set ​ d = FPdec(k,c)

if the left $\sigma$ bits of d are s then output the right L bits of d, else output $\bot$

Security should hold even if the adversary chooses $s$; you making it part of the key (in particular, random and secret) might reduce the impact of an attack on the underlying FPE scheme.

Depending on your use-case, you may be able to support a tweak. ​ The right FPE scheme depends on how 2$^{\sigma+L}$ compares to your upper bound the number of distinct [queries which are not just the opposite direction to an earlier query] (for any single tweak, if applicable).

The ​ low-query , medium-query , high-query ​ regimes are handled by

Generalized Feistel , swap-or-not , sometimes-recurse shuffle ​ respectively.

(I don't know whether-or-not they mention tweakability, but there's a simple generic

way to make any encryption scheme tweakable, which I can describe if you'd like.)

The main reason for using FPE rather than just a MAC is that

it essentially removes the adversary's control over the effects

of a successful forgery (thus perhaps allowing a shorter tag).

For example, with AES-CTR on a known plaintext, the adversary can

choose exactly what the decryption result will be if they guess the right tag.

A much-less-important reason is that forgery probability is in

fact slightly lower, since the guesses are nearly-independent.

Should I formalize either of those things?

If your scheme can be stateful, then you can further make it so that after any

attempted altering of what's sent (whether it's a replay or a re-ordering or just

a fresh cipher-block, and whether-or-not the attempt succeeds at forging),

[decryptions after the decryption of the initial tampering]

are indistinguishable from being independent with

$\big[\big[$probability ​ $1\hspace{-0.05 in}-\hspace{-0.03 in}\left(1/\hspace{-0.03 in}\left(2^{\sigma}\right)\right)$ ​ of outputting $\bot \big]$ ​ ​ ​ and

$\big[$probability $1/\hspace{-0.03 in}\left(2^{\sigma}\right)$ of outputting a random L-bit string$\big]\big]$ .

Should I explain how to do that?